clustAnalytics: Cluster Evaluation on Graphs

Description

Evaluates the stability and significance of clusters on 'igraph' graphs. Supports weighted and unweighted graphs. Implements the cluster evaluation methods defined by Arratia A, Renedo M (2021) doi:10.7717/peerj-cs.600. Also includes an implementation of the Reduced Mutual Information introduced by Newman et al. (2020) doi:10.1103/PhysRevE.101.042304.

See Also

Useful links:

• https://github.com/martirm/clustAnalytics

• Report bugs at https://github.com/martirm/clustAnalytics/issues

FOMD (Fraction Over Median Degree)

Description

Given a weighted graph and a partition into communities, returns the fraction of nodes of each community whose internal degree (i.e. the degree accounting only intra-community edges) is greater than the median degree of the whole graph.

Usage

FOMD(g, com, edgelist = NULL)

Arguments

Value

Numeric vector with the FOMD of each community.

See Also

Other cluster scoring functions: average_degree(), average_odf(), conductance(), coverage(), cut_ratio(), density_ratio(), edges_inside(), expansion(), internal_density(), max_odf(), normalized_cut(), scoring_functions(), weighted_clustering_coefficient(), weighted_transitivity()

Examples

data(karate, package="igraphdata")
FOMD(karate, membership(cluster_louvain(karate)))

Estimates |H_i|/|H_(i+1)| for the first n_rows rows

Description

Estimates |H_i|/|H_(i+1)| for the first n_rows rows

Usage

H_fractions_rows(M, n_rows, error = 0.01)

Arguments

Value

vector with all the |H_i|/|H_(i+1)| fractions

Applies function to each subgraph of a graph

Description

Applies function to each subgraph of a graph

Usage

apply_subgraphs(g, com, f, ...)

Arguments

Value

vector with the result of each subgraph

Examples

data(karate, package="igraphdata")
apply_subgraphs(g=karate, com=V(karate)$Faction, f=gorder)

Auxiliary Functions of a Graph Partition

Description

Given a weighted graph and a partition into communities, returns the internal edge weight, the size, and the cut weight for each community.

Usage

auxiliary_functions(g, com, edgelist)

Arguments

Average Degree

Description

Average degree (weighted degree, if the graph is weighted) of a graph's communities.

Usage

average_degree(g, com)

Arguments

Value

Numeric vector with the average degree of each community.

See Also

Other cluster scoring functions: FOMD(), average_odf(), conductance(), coverage(), cut_ratio(), density_ratio(), edges_inside(), expansion(), internal_density(), max_odf(), normalized_cut(), scoring_functions(), weighted_clustering_coefficient(), weighted_transitivity()

Examples

data(karate, package="igraphdata")
average_degree(karate, membership(cluster_louvain(karate)))

Average Out Degree Fraction

Description

Computes the Average Out Degree Fraction (Average ODF) of a graph (which can be weighted) and its communities.

Usage

average_odf(g, com)

Arguments

Value

Numeric vector with the Average ODF of each community.

See Also

Other cluster scoring functions: FOMD(), average_degree(), conductance(), coverage(), cut_ratio(), density_ratio(), edges_inside(), expansion(), internal_density(), max_odf(), normalized_cut(), scoring_functions(), weighted_clustering_coefficient(), weighted_transitivity()

Examples

data(karate, package="igraphdata")
average_odf(karate, membership(cluster_louvain(karate)))

Generates a Barabási-Albert graph with community structure

Description

Generates a Barabási-Albert graph with community structure

Usage

barabasi_albert_blocks(
  m,
  p,
  B,
  t_max,
  G0 = NULL,
  t0 = NULL,
  G0_labels = NULL,
  sample_with_replacement = FALSE,
  type = "Hajek"
)

Arguments

Value

The resulting graph, as an igraph object. The vertices have a "label" attribute.

Examples

B <- matrix(c(1, 0.2, 0.2, 1), ncol=2)
G <- barabasi_albert_blocks(m=4, p=c(0.5, 0.5), B=B, t_max=100, type="Hajek", 
                            sample_with_replacement = FALSE)

Performs nonparametric bootstrap to a graph and a list of clustering algorithms

Description

Performs nonparametric bootstrap on a graph's by resampling its vertices and clustering the results using a list of clustering algorithms.

Usage

boot_alg_list(
  alg_list = list(Louvain = cluster_louvain, `label prop` = cluster_label_prop, walktrap
    = cluster_walktrap),
  g,
  R = 999,
  return_data = FALSE,
  type = "global"
)

Arguments

Value

If return_data is set to TRUE, returns a list of objects of class "boot" (see boot). Otherwise, returns as table with the mean distances from the clusters in the original graph to the resampled ones, for each of the algorithms.

Contingency table from membership vectors

Description

Given two membership vectors, returns the corresponding contingency table. we assume the labels are >=1 and numbered consecutively. If not consecutive (some labels are unused) this implementation still works, but will be less efficient.

Usage

c_rs_table(c1, c2)

Arguments

Conductance

Description

Conductance of a graph's communities, which is given by

\frac{c_s}{2m_s + c_s}

, where c_s is the weight of the edges connecting the community s to the rest of the graph, and m_s is the internal weight of the community.

Usage

conductance(g, com)

Arguments

Value

Numeric vector with the conductance of each community.

See Also

Other cluster scoring functions: FOMD(), average_degree(), average_odf(), coverage(), cut_ratio(), density_ratio(), edges_inside(), expansion(), internal_density(), max_odf(), normalized_cut(), scoring_functions(), weighted_clustering_coefficient(), weighted_transitivity()

Examples

data(karate, package="igraphdata")
conductance(karate, membership(cluster_louvain(karate)))

Computes possible membership vectors from contingency table

Description

Given a contingency table, obtains a possible pair of corresponding labelings. That is, element M[i,j] is the number of elements that belong to community i in the first labeling and j in the second.

Usage

contingency_to_membership_vectors(M)

Arguments

Value

a list containing the two membership vectors

Natural logarithm of the number of contingency tables

Description

Given a contingency table, returns the natural logarithm of the number of contingency tables that share the same column and row sums. This implementation combines a Markov Chain Monte Carlo approximation with an analytical formula. The input can be either M a contingency table, or two vectors of labels c1 and c2 (in this case, we are counting contingency tables with the same column an row sums as the one produced by c1 and c2)

Usage

count_contingency_tables_log(c1, c2, M = NULL, monte_carlo_only = FALSE)

Arguments

Coverage

Description

Computes the coverage (fraction of internal edges with respect to the total number of edges) of a graph and its communities

Usage

coverage(g, com)

Arguments

Value

Numeric value of the coverage of g and com.

See Also

Other cluster scoring functions: FOMD(), average_degree(), average_odf(), conductance(), cut_ratio(), density_ratio(), edges_inside(), expansion(), internal_density(), max_odf(), normalized_cut(), scoring_functions(), weighted_clustering_coefficient(), weighted_transitivity()

Examples

data(karate, package="igraphdata")
coverage(karate, membership(cluster_louvain(karate)))

Cut Ratio

Description

The cut ratio of a graph's community is the total edge weight connecting the community to the rest of the graph divided by number of unordered pairs of vertices such that one belongs to the community and the other does not.

Usage

cut_ratio(g, com)

Arguments

Value

Numeric vector with the cut ratio of each community.

See Also

Other cluster scoring functions: FOMD(), average_degree(), average_odf(), conductance(), coverage(), density_ratio(), edges_inside(), expansion(), internal_density(), max_odf(), normalized_cut(), scoring_functions(), weighted_clustering_coefficient(), weighted_transitivity()

Examples

data(karate, package="igraphdata")
cut_ratio(karate, membership(cluster_louvain(karate)))

Density Ratio

Description

Density ratio of a graph's communities.

Usage

density_ratio(g, com, type = "local")

Arguments

Value

Numeric vector with the internal density of each community.

See Also

Other cluster scoring functions: FOMD(), average_degree(), average_odf(), conductance(), coverage(), cut_ratio(), edges_inside(), expansion(), internal_density(), max_odf(), normalized_cut(), scoring_functions(), weighted_clustering_coefficient(), weighted_transitivity()

Examples

data(karate, package="igraphdata")
density_ratio(karate, membership(cluster_louvain(karate)))

Edges Inside

Description

Number of edges inside a graph's communities, or their accumulated weight if the graph's edges are weighted.

Usage

edges_inside(g, com)

Arguments

Value

Numeric vector with the internal edge weight of each community

See Also

Other cluster scoring functions: FOMD(), average_degree(), average_odf(), conductance(), coverage(), cut_ratio(), density_ratio(), expansion(), internal_density(), max_odf(), normalized_cut(), scoring_functions(), weighted_clustering_coefficient(), weighted_transitivity()

Examples

data(karate, package="igraphdata")
edges_inside(karate, membership(cluster_louvain(karate)))

Estimates |H_0|/|H_r*|

Description

This is the total number of contingency tables (of the same margins as M) divided by the number that match M until the r-th row (included, 0-indexed). Note that if r==0, this is always 1 by definition.

Usage

estimate_H_fraction_r_rows(M, r, error = 0.1)

Arguments

Estimates |H_i|/|H_{i+1}| for the first r rows

Description

The product of all these ratios is is the total number of contingency tables (of the same margins as M) divided by the number that match M until the r-th row (included, 0-indexed).

Usage

estimate_H_fractions(M, r, error = 0.1)

Arguments

Value

NumericVector containing all the ratios

Evaluates significance of cluster algorithm results on a graph

Description

Given a graph and a list of clustering algorithms, computes several scoring functions on the clusters found by each of the algorithms.

Usage

evaluate_significance(
  g,
  alg_list = list(Louvain = cluster_louvain, `label prop` = cluster_label_prop, walktrap
    = cluster_walktrap),
  no_clustering_coef = FALSE,
  gt_clustering = NULL,
  w_max = NULL
)

Arguments

Value

A data frame with the values of scoring functions (see scoring_functions) of the clusters obtained by applying the clustering algorithms to the graph.

Examples

data(karate, package="igraphdata")
evaluate_significance(karate)

Evaluates the significance of a graph's clusters

Description

Computes community scoring functions to the communities obtained by applying the given clustering algorithms to a graph. These are compared to the same scores for randomized versions of the graph obtained by a switching algorithm that rewires edges.

Usage

evaluate_significance_r(
  g,
  alg_list = list(Louvain = cluster_louvain, `label prop` = cluster_label_prop, walktrap
    = cluster_walktrap),
  no_clustering_coef = FALSE,
  gt_clustering = NULL,
  table_style = "default",
  ignore_degenerate_cl = TRUE,
  Q = 100,
  lower_bound = 0,
  weight_sel = "const_var",
  n_reps = 5,
  w_max = NULL
)

Arguments

Value

A matrix with the results of each scoring function and algorithm. See table_style for details.

Expansion

Description

Given a graph (possibly weighted) split into communities, the expansion of a community is the sum of all edge weights connecting it to the rest of the graph divided by the number of vertices in the community

Usage

expansion(g, com)

Arguments

Value

Numeric vector with the expansion of each community.

See Also

Other cluster scoring functions: FOMD(), average_degree(), average_odf(), conductance(), coverage(), cut_ratio(), density_ratio(), edges_inside(), internal_density(), max_odf(), normalized_cut(), scoring_functions(), weighted_clustering_coefficient(), weighted_transitivity()

Examples

data(karate, package="igraphdata")
expansion(karate, membership(cluster_louvain(karate)))

Forex correlation network

Description

Network built from correlations between time series of exchange rate returns. It was built from the 13 most traded currencies and with data of January 2009. It is a complete graph of 78 vertices (corresponding to pairs of currencies) and has edge weights bounded between 0 and 1.

Usage

g_forex

Format

An igraph object with 78 vertices and 3003 weighted edges

Returns edgelist with weights from a weighted igraph graph

Description

This function is just used internally for testing the package

Usage

igraph_to_edgelist(g, sort = TRUE)

Arguments

Value

A matrix where the first two columns indicate the incident vertices, and the third is the weight of the corresponding edge.

Internal Density

Description

Internal density of a graph's communities. That is, the sum of weights of their edges divided by the number of unordered pairs of vertices (which is the number of potential edges).

Usage

internal_density(g, com)

Arguments

Value

Numeric vector with the internal density of each community.

See Also

Other cluster scoring functions: FOMD(), average_degree(), average_odf(), conductance(), coverage(), cut_ratio(), density_ratio(), edges_inside(), expansion(), max_odf(), normalized_cut(), scoring_functions(), weighted_clustering_coefficient(), weighted_transitivity()

Examples

data(karate, package="igraphdata")
internal_density(karate, membership(cluster_louvain(karate)))

Approximation of log(omega(a,b))

Description

Where omega(a,b) is the number of contingency tables with a, b as row and column sums. This approximation is only good for dense tables.

Usage

log_omega_estimation(c1, c2, base = exp(1))

Arguments

Make graph weighted

Description

Given a graph, create a "weight" attribute set to 1 for the edges if it doesn't exist already.

Usage

make_graph_weighted(g)

Arguments

Value

igraph graph with either all edge weights set to 1 (if the original graph was unweighted), or to their original weights if they already existed (in this case, the graph isn't modified at all).

Max Out Degree Fraction

Description

Computes the Maximum Out Degree Fraction (Max ODF) of a graph (which can be weighted) and its communities.

Computes the Flake Out Degree Fraction (Max ODF) of a graph (which can be weighted) and its communities.

Usage

max_odf(g, com)

max_odf(g, com)

Arguments

Value

Numeric vector with the Max ODF of each community.

Numeric vector with the Max ODF of each community.

See Also

Other cluster scoring functions: FOMD(), average_degree(), average_odf(), conductance(), coverage(), cut_ratio(), density_ratio(), edges_inside(), expansion(), internal_density(), normalized_cut(), scoring_functions(), weighted_clustering_coefficient(), weighted_transitivity()

Other cluster scoring functions: FOMD(), average_degree(), average_odf(), conductance(), coverage(), cut_ratio(), density_ratio(), edges_inside(), expansion(), internal_density(), normalized_cut(), scoring_functions(), weighted_clustering_coefficient(), weighted_transitivity()

Examples

data(karate, package="igraphdata")
max_odf(karate, membership(cluster_louvain(karate)))
data(karate, package="igraphdata")
max_odf(karate, membership(cluster_louvain(karate)))

Normalized cut

Description

Normalized cut of a graph's communities, which is given by

\frac{c_s}{2m_s+c_s}+\frac{c_s}{2(m-m_s)+c_s}

, where c_s is the weight of the edges connecting the community s to the rest of the graph, m_s is the internal weight of the community, and m is the total weight of the network.

Usage

normalized_cut(g, com)

Arguments

Value

Numeric vector with the normalized cut of each community.

See Also

Other cluster scoring functions: FOMD(), average_degree(), average_odf(), conductance(), coverage(), cut_ratio(), density_ratio(), edges_inside(), expansion(), internal_density(), max_odf(), scoring_functions(), weighted_clustering_coefficient(), weighted_transitivity()

Examples

data(karate, package="igraphdata")
normalized_cut(karate, membership(cluster_louvain(karate)))

Maximum, Average, and Flake Out Degree Fractions of a Graph Partition

Description

Given a weighted graph and a partition into communities, returns the maximum, average and flake out degree fractions of each community.

Usage

out_degree_fractions(g, com, edgelist)

Arguments

Value

A numeric matrix where each row corresponds to a community, and the columns contain the max, average and flake ODFs respectively.

Reduced Mutual Information

Description

Computes the Newman's Reduced Mutual Information (RMI) as defined in (Newman et al. 2020).

Usage

reduced_mutual_information(
  c1,
  c2,
  base = 2,
  normalized = FALSE,
  method = "approximation2",
  warning = TRUE
)

Arguments

Details

The implementation is based on equations 23 (25 for the normalized case) and 29 in (Newman et al. 2020). The evaluations of the \Gamma functions can get too large and cause overflow issues in the intermediate steps, so the following term of equation 29:

\frac{1}{2} \log \frac{\Gamma(\mu R) \Gamma(\nu S)} {(\Gamma(\nu)\Gamma(R))^S (\Gamma(\mu)\Gamma(S))^R }

is rewritten as

\frac{1}{2} (\log\Gamma(\mu R) + \log\Gamma(\nu S) - S\log(\Gamma(\nu) - S\log(\Gamma(R) - R\log\Gamma(\mu) - R\log\Gamma(R) )

, and then the function lgamma is used instead of gamma.

Value

The value of Newman's RMI (a scalar).

References

Newman MEJ, Cantwell GT, Young J (2020). “Improved mutual information measure for clustering, classification, and community detection.” Phys. Rev. E, 101(4), 042304. doi:10.1103/PhysRevE.101.042304.

Relabels membership vector

Description

Takes a vector of vertex ids indicating community membership, and relabels the communities to have consecutive values from 1 to the number of communities.

Usage

relabel(c)

Arguments

Value

A numeric vector of consecutive vertex ids starting from one

Randomizes a weighted graph while keeping the degree distribution constant.

Description

Converts the graph to a weighted edge list in NumericMatrix, which is compatible with Rcpp. The Rcpp function "randomize" is called, and then the resulting edge list is converted back into an igraph object.

Usage

rewireCpp(
  g,
  Q = 100,
  weight_sel = "max_weight",
  lower_bound = 0,
  upper_bound = NULL
)

Arguments

Value

The rewired graph.

Scoring Functions of a Graph Partition

Description

Computes the scoring functions of a graph and its clusters.

Usage

scoring_functions(
  g,
  com,
  no_clustering_coef = TRUE,
  type = "local",
  weighted = TRUE,
  w_max = NULL
)

Arguments

Value

If type=="local", returns a dataframe with a row for each community, and a column for each score. If type=="global", returns a single row with the weighted average scores.

See Also

Other cluster scoring functions: FOMD(), average_degree(), average_odf(), conductance(), coverage(), cut_ratio(), density_ratio(), edges_inside(), expansion(), internal_density(), max_odf(), normalized_cut(), weighted_clustering_coefficient(), weighted_transitivity()

Examples

data(karate, package="igraphdata")
scoring_functions(karate, membership(cluster_louvain(karate)))

Sort matrix

Description

Given a matrix, rearranges rows and columns so that row sums and col sums end up in ascending order.

Usage

sort_matrix(M)

Arguments

Value

rearranged matrix

Triangle Participation Ratio (community-wise)

Description

Computes the triangle participation ratio (proportion of vertices that belong to a triangle). The computation is done to the subgraphs induced by each of the communities in the given partition.

Usage

triangle_participation_ratio_communities(g, com)

Arguments

Value

A vector containing the triangle participation ratio of each community.

Performs a step of the Markov Chain Monte Carlo method

Description

Modifies the matrix while keeping the column and row sums constant, as well as leaving the positions strictly preceding (k,l) in lexicographical order invariant.

Usage

walk_step(M, k, l)

Arguments

Value

boolean indicating whether the step left the matrix invariant

Weighted clustering coefficient of a weighted graph.

Description

Weighted clustering Computed using the definition given by McAssey, M. P. and Bijma, F. in "A clustering coefficient for complete weighted networks" (2015).

Usage

weighted_clustering_coefficient(g, upper_bound = NULL)

Arguments

Value

The weighted clustering coefficient of the graph (a scalar).

See Also

Other cluster scoring functions: FOMD(), average_degree(), average_odf(), conductance(), coverage(), cut_ratio(), density_ratio(), edges_inside(), expansion(), internal_density(), max_odf(), normalized_cut(), scoring_functions(), weighted_transitivity()

Examples

data(karate, package="igraphdata")
weighted_clustering_coefficient(karate)

Weighed transitivity of a weighted graph.

Description

Computed using the definition given by McAssey, M. P. and Bijma, F. in "A clustering coefficient for complete weighted networks" (2015).

Usage

weighted_transitivity(g, upper_bound = NULL)

Arguments

Value

The weighted transitivity of the graph (a scalar).

See Also

Other cluster scoring functions: FOMD(), average_degree(), average_odf(), conductance(), coverage(), cut_ratio(), density_ratio(), edges_inside(), expansion(), internal_density(), max_odf(), normalized_cut(), scoring_functions(), weighted_clustering_coefficient()

Examples

data(karate, package="igraphdata")
weighted_transitivity(karate)