Communities: Community detection algorithms and evaluation functions

In multinet: Analysis and mining of multilayer social networks

Community detection algorithms and evaluation functions

Description

Various algorithms to compute communities in multiplex networks, based on flattening (flat_ec, weighted, and flat_wc, unweighted), frequent itemset mining (abacus), adjacent cliques (clique percolation), modularity optimization (generalized louvain), random walks (infomap) and label propagation (mdlp). glouvain2_ml is a more efficient implementation of the original glouvain_ml, no longer based on matrices: it is equivalent to glouvain_ml with gamma set by default to 1.0 (apart from undeterministic behaviour: individual executions are not guaranteed to return the same result). get_community_list_ml is a commodity function translating the result of these algorithms into a list of vertex identifiers, and is internally used by the plotting function.

There are also algorithms to evaluate the resulting communities: generalized modularity (as optimized by glouvain) and normalized mutual information (nmi_ml) and omega index (omega_index_ml) to compare respectively partitioning and general communities. Please consider that both comparison functions use the number of vertices in the network to make a computation, so the absence of actors from some layers would change their result.

Usage

abacus_ml(n, min.actors=3, min.layers=1)
flat_ec_ml(n)
flat_nw_ml(n)
clique_percolation_ml(n, k=3, m=1)
glouvain_ml(n, gamma=1, omega=1)
infomap_ml(n, overlapping=FALSE, directed=FALSE, self.links=TRUE)
mdlp_ml(n)

modularity_ml(n, comm.struct, gamma=1, omega=1)
nmi_ml(n, com1, com2)
omega_index_ml(n, com1, com2)
get_community_list_ml(comm.struct, n)

Arguments

n	A multilayer network.
min.actors	Minimum number of actors to form a community.
min.layers	Minimum number of times two actors must be in the same single-layer community to be considered in the same multi-layer community.
k	Minimum number of actors in a clique. Must be at least 3.
m	Minimum number of common layers in a clique. Not to be confused with number of edges, as it is meant in the summary function (here we use the notation of the paper introducing this algorithm).
gamma	Resolution parameter for modularity in the generalized louvain method.
omega	Inter-layer weight parameter in the generalized louvain method.
overlapping	Specifies if overlapping clusters can be returned.
directed	Specifies whether the edges should be considered as directed.
self.links	Specifies whether self links should be considered or not.
comm.struct	The result of a community detection method.
com1	The result of a community detection method.
com2	The result of a community detection method.

Value

All community detection algorithms return a data frame where each row contains actor name, layer name and community identifier.

abacus_ml, flat_ec_ml, flat_nw_ml, clique_percolation_ml, and glouvain_ml are only implemented to work with undirected networks. clique_percolation_ml automatically considers the network to be undirected even if the edges are directed. glouvain_ml also considers weights, if *all* layers have a DOUBLE attribute named w_.

The evaluation functions return a number between -1 and 1. For the comparison functions, 1 indicates that the two community structures are equivalent. The maximum possible value of modularity is <= 1 and depends on the network, so modularity results should not be compared across different networks. Also, notice that modularity is only defined for partitioning community structures.

get_community_list_ml transforms the output of a community detection function into a list by grouping all the nodes having the same community identifier and the same layer. Notice that:

• The numbers in the result of get_community_list_ml() correspond to vertices. Number X refers the the Xth vertex as returned by vertices_ml(ml).

• This function splits the communities by layer. That is, every community corresponds to multiple entry in the generated list (in general), all with the same value of $cid.

References

• Berlingerio, Michele, Pinelli, Fabio, and Calabrese, Francesco (2013). ABACUS: frequent pAttern mining-BAsed Community discovery in mUltidimensional networkS. Data Mining and Knowledge Discovery, 27(3), 294-320. (for abacus_ml())

• Afsarmanesh, Nazanin, and Magnani, Matteo (2018). Partial and overlapping community detection in multiplex social networks. Social informatics (for clique_percolation_ml())

• Mucha, Peter J., Richardson, Thomas, Macon, Kevin, Porter, Mason A., and Onnela, Jukka-Pekka (2010). Community structure in time-dependent, multiscale, and multiplex networks. Science (New York, N.Y.), 328(5980), 876-8. Data Analysis, Statistics and Probability; Physics and Society. (for glouvain_ml())

• Michele Berlingerio, Michele Coscia, and Fosca Giannotti. Finding and characterizing communities in multidimensional networks. In International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pages 490-494. IEEE Computer Society Washington, DC, USA, 2011 (for flat_ec_ml() and flat_nw_ml())

• De Domenico, M., Lancichinetti, A., Arenas, A., and Rosvall, M. (2015) Identifying Modular Flows on Multilayer Networks Reveals Highly Overlapping Organization in Interconnected Systems. PHYSICAL REVIEW X 5, 011027 (for infomap_ml())

• Oualid Boutemine and Mohamed Bouguessa. Mining Community Structures in Multidimensional Networks. ACM Transactions on Knowledge Discovery from Data, 11(4):1-36, 2017 (for mdlp_ml())

See Also

multinet.plotting

Examples

net <- ml_florentine()
abacus_ml(net)
flat_ec_ml(net)
flat_nw_ml(net)
clique_percolation_ml(net)
glouvain_ml(net)
infomap_ml(net)
mdlp_ml(net)

# evaluation

c1 <- glouvain_ml(net)
modularity_ml(net, c1)

c2 <- flat_ec_ml(net)
nmi_ml(net, c1, c2)

c3 <- abacus_ml(net)
omega_index_ml(net, c1, c2)

multinet documentation built on Nov. 2, 2024, 5:06 p.m.