FuzzyMod {CliquePercolation}

Fuzzy Modularity of a community structure of a graph

Description

Function calculates the fuzzy modularity of a (disjoint or non-disjoint division) of a graph into subgraphs.

Usage

FuzzyMod(graph, membership, abs = TRUE)

Arguments

graph

The input graph.

membership

Numeric vector or list indicating the membership structure.

abs

Should fuzzy modularity be calculated based on absolute values of network edges? Default is TRUE.

Details

The modularity of a graph with respect to some division is a measure of how good the division is. The traditional modularity Q was proposed by Newman and Girvan (2004):

Q=\frac{1}{2m} \sum_{c\epsilon_C} \sum_{u,v\epsilon_V} (A_{uv}-\frac{k_{u}k_{v}}{2m}) \delta_{cu} \delta_{cv}

where m is the total number of edges, C is the set of communities corresponding to a partition, V is the set of vertices (i.e. nodes) in the network, A_{uv} is the element of the A adjacency matrix in row i and column j, and k_{u} and k_{v} are the node degrees of nodes u and v, respectively. \delta_{cu} indicates whether node u belongs to community c, which equals 1 if u and v belongs to community c and 0 otherwise. The product \delta_{cu}*\delta_{cv} is a Kronecker delta function which equals 1 if u and v belongs to community c and 0 otherwise.

In the case of weighted networks, Fan, Li, Zhang, Wu, and Di (2007) proposed that to calculate modularity Q, m should be the total edge weights, and k_{u} and k_{v} should be the node strengths of nodes u and v, respectively.

One limitation of modularity Q proposed by Newman and Girvan (2004) was that modularity could not be calculated for non-disjoint community partitions (i.e. networks in which a node is assigned to more than one community). As such, Chen, Shang, Lv, and Fu (2010) proposed a generalisation in terms of fuzzy modularity:

Q=\frac{1}{2m} \sum_{c\epsilon_C} \sum_{u,v\epsilon_V} \alpha_{cu} \alpha_{cv} (A_{uv}-\frac{k_{u}k_{v}}{2m})

where \alpha_{cu} is the belonging coefficient. The belonging coefficient reflects how much the node u belongs to community c. The belonging coefficient is calculated as:

\alpha_{cu} = \frac{k_{cu}}{\sum_{c\epsilon_C}k_{cu}}

In case of a disjoint solution, the fuzzy modularity Q proposed by Chen, Shang, Lv, and Fu (2010) reduces to the modularity Q proposed by Newman and Girvan (2004).

Value

A numeric scalar, the fuzzy modularity score of the given configuration.

Author(s)

Pedro Henrique Ribeiro Santiago, [e-mail] [ctb]

Gustavo Hermes Soares, [rev]

Adrian Quintero, [rev]

Lisa Jamieson, [rev]

References

Newman, M. E., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical review E, 69(2), 026113.

Fan, Y., Li, M., Zhang, P., Wu, J., & Di, Z. (2007). Accuracy and precision of methods for community identification in weighted networks. Physica A: Statistical Mechanics and its Applications, 377(1), 363-372.

Chen, D., Shang, M., Lv, Z., & Fu, Y. (2010). Detecting overlapping communities of weighted networks via a local algorithm. Physica A: Statistical Mechanics and its Applications, 389(19), 4177-4187.

Examples

g <- igraph::disjoint_union(igraph::make_full_graph(5),igraph::make_full_graph(4))
g <- igraph::add_edges(g, c(2,6, 2,7, 2,8, 2,9))
wc <- list(c(1,2,3,4,5),c(2,6,7,8,9))
FuzzyMod(graph=g, membership=wc, abs=TRUE)