1 Introduction
1.1 Background
Name | Parameters | Complexity | Strategy |
---|---|---|---|
GN (Girvan and Newman 2002) | – | \(O(nm^2 )\) | Removal of edges with maximum betweenness |
FN, CNM (Girvan and Newman 2002) | – | \(O(n^2)\), \(O(n\log ^2n)\) | Greedy modularity maximization |
LPA (Raghavan et al. 2007) | i | O(n) | Label propagation |
EM (Newman and Leicht 2007) | k, i | O(nki) | Probabilistic mixture models |
SCAN (Xu et al. 2007) | \(\varepsilon ,\mu \) | O(n) | Structural clustering |
Louvain (Blondel et al. 2008) | – | \(O(n\log n)\) | Multilevel modularity maximization |
LFM (Lancichinetti et al. 2009) | \(\alpha \) | \(O(n^2\log n)\) | Local optimization |
\(\tau \) | \(O(m(n+m))\) | Information compression | |
NMF (Zhang et al. 2007) | – | \(O(hkn^2)\) | Nonnegative matrix factorization |
1.2 Main contributions
1.3 Outline of the paper
2 Models
-
Ordinal layers. The layers are sorted by a certain order, in which the interlayer edges connect the corresponding nodes in the adjacent layers. Take temporal networks for example, there are numerous layers representing different snapshots, but the order of layers is decided by the time sequence.
-
Categorical layers. The layers are classified into several groups, where each group represents a type of interaction.
2.1 Definitions
Symbol | Scenario | Description |
---|---|---|
\({\mathcal {R}}\) | General definitions | Set of real numbers |
G | Monolayer | A graph or a monolayer network |
n | Monolayer | The number of nodes |
m | Monolayer | The number of edges |
V | Monolayer | Node set in a graph or monolayer networks |
E | Monolayer | Edge set in a graph or monolayer networks |
\(k_i\) | Monolayer | The degree of node i |
\(\varGamma (i)\) | Monolayer | The neighbors of node i |
Q | Monolayer | Modularity (Newman and Girvan 2004) |
D | Monolayer | Modularity density (Li et al. 2008) |
S | Monolayer | Surprise (Aldecoa and Marín 2011) |
L | Multilayer | The total number of layers |
\({\mathcal {G}}\) | Multilayer | A multilayer network comprised of graphs |
\({\mathcal {C}}\) | Multilayer | Collection of interlayer edges |
\(\alpha \) | Multilayer | Aspect (Kivelä et al. 2014) or layer |
\(G_\alpha \) | Multilayer | A graph of layer \(\alpha \) |
\(V_\alpha \) | Multilayer | Node set in layer \(\alpha \) |
\(E_\alpha \) | Multilayer | Edge set in a layer \(\alpha \) |
\({\mathcal {L}}\) | Multilayer | Collection of layers |
\({\mathcal {L}}_\alpha \) | Multilayer | Elementary layer \(\alpha \) |
\({\mathcal {M}}\) | Multilayer | Multilayer network model |
\({\check{M}}\) | Multilayer | The supra-adjacency matrix |
\(A_\alpha \) | Multilayer | The adjacency matrix of layer \(\alpha \) |
\(I_{\alpha \beta }\) | multilayer | The interlayer edges between layer \(\alpha \) and \(\beta \) |
\(k_i^\alpha \) | Multilayer | The degree of node i in layer \(\alpha \) |
\(Q_M\) | Multilayer | Modularity for multiplex networks |
\(\rho _c\) | Miscellaneous | Redundancy index |
\(\delta \) | Miscellaneous | Kronecker delta |
2.2 Features
2.2.1 Centrality
2.2.2 Correlations
3 Methods
3.1 Problem statement
3.2 Evaluation functions
3.2.1 Modularity, modularity density, performance and surprise
3.2.2 MDL, Pareto frontier and redundancy
3.2.3 Purity, NMI, and ARI
3.3 Algorithms classification
-
Flattening methods
-
Aggregation methods
-
Direct methods
3.3.1 Improved label propagation algorithm
-
Nodes are ordered randomly;
-
For each node u, each marked similar neighbor sends out its label to u, and mark the node u with maximum labels.
Metric in monolayer networks | Modification for multilayer networks |
---|---|
\(\text {JC}(i, j)=\frac{|\varGamma (i) \cap \varGamma (j)|}{|\varGamma (i) \cup \varGamma (j)|}\) | \(\frac{\sum _{\alpha =1}^{L}\left( \frac{1}{2 \omega _{\alpha }}(\frac{|N|}{|U|}+\frac{|\acute{N}|}{|\acute{U}|})\right) }{\sum _{\alpha =1}^{L} \omega _{\alpha }}\) |
\(\text {CN}(i, j)=|\varGamma (i) \cap \varGamma (j)|\) | \(\frac{\sum _{\alpha =1}^{L}\left( \frac{1}{2 \omega _{\alpha }}(|N|+|\acute{N}|)\right) }{\sum _{\alpha =1}^{L} \omega _{\alpha }}\) |
\(\text {AA}(i, j)=\sum _{z \in |\varGamma (i) \cap \varGamma (j)|} \frac{1}{\log k_{z}}\) | \(\frac{\sum _{\alpha =1}^{k}\left( \frac{1}{2 \omega _{\alpha }}(\sum _{z \in N} \frac{1}{\log \left| \varGamma _{z}^{\alpha }\right| }+\sum _{z \in \acute{N}} \frac{1}{\log \left| \varGamma _{z}^{\alpha }\right| })\right) }{\sum _{\alpha =1}^{L} \omega _{\alpha }}\) |
3.3.2 Nonnegative matrix factorization methods
3.3.3 Random walk methods
3.3.4 Multi-objective optimization methods
3.4 Discussion
Name | Classification | Strategy | Complexity \(^a\) | Network |
---|---|---|---|---|
PMM (Tang et al. 2009) | Aggregation | Multilayer modularity maximization | \(O(n^3L)\) | Multi-dimensional |
MULTICLUS (Papalexakis et al. 2013) | Aggregation | Minimum description length | \(O(mnIC^2)\) | Multiplex, bipartite |
GRAPHFUSE (Papalexakis et al. 2013) | Aggregation | Tensor analysis | \(O(n^3L)\) | Multiplex |
ABACUS (Berlingerio et al. 2013) \(^{b}\) | Aggregation | Multilayer modularity maximization | – | Multi-dimensional |
DNMF (Jiao et al. 2017) | Aggregation | Nonnegative matrix factorization | \(O(n^2L)\) | Multiplex, temporal |
EMCD (Tagarelli et al. 2017) \(^{c}\) | Aggregation | Modularity maximization | \(O(I(m+LC))\) | Multiplex |
Multilink (Mondragon et al. 2018) | Aggregation | Multilink similarity | \(O(m^2)\) | Multiplex |
M-EMCD* (Mandaglio et al. 2018) | Aggregation | Modularity maximization | \(O(I(m+LC))\) | Multiplex |
M-Motif (Huang et al. 2019) | Aggregation | Merge partitions across layers | \(O(n\log (n)L^2)\) | Multilayer |
MEMM (Zhang et al. 2019) | Aggregation | Multilayer edge mixture model | \(O(n^2)\) | Multiplex |
HSBM (Paez et al. 2019) | Aggregation | Hierarchical SBM and Bayes | \(O(n^2LC^2)\) | Multiplex |
Variational-Bayes (Ali et al. 2019) | Aggregation | SBM and variational Bayes | \(O(n^2L^2C^)\) | Multiplex, weighted |
GenLouvain (Jutla et al. 2011) | Direct | Multiplex map equation | \(O(n^2 \log n)\) | Multiplex, temporal |
MultiGA (Amelio and Pizzuti 2014b) | Direct | Genetic representation | \(O(In^2L)\) | Multiplex |
MultiMOGA (Amelio and Pizzuti 2014a) | Direct | Multi-objective optimization | \(O(LCn^2)\) | Multiplex |
CLAN (Dabideen et al. 2014) | Direct | Variational label propagation | O(LInK) | Multiplex, temporal |
LART (Kuncheva and Montana 2015) | Direct | Random walk | \(O(m^3)\) | Multiplex |
Multiplex-Infomap (De Domenico et al. 2015a) | Direct | Multiplex map equation | \(O(n^2 )\) | Multiplex |
LocalNCPs (Jeub et al. 2015) \(^{d}\) | Direct | Local random walk | \(\ge O(nIKL)\) | Multiplex |
BAZZI (Bazzi et al. 2016) | Direct | Multilayer modularity maximization | \(O(nI^2L)\) | Multiplex, temporal |
ML-LCD (Interdonato et al. 2017) | Direct | Local objective function maximization | \(\ge O(C^3K^2L)\) | Multiplex |
GN-\(Q_M\) (Pramanik et al. 2017) | Direct | Maximum betweenness edges removal | \(O(nm^2)\) | Multiplex |
Louvain-\(Q_M\) (Pramanik et al. 2017) | Direct | Modularity optimization | \(O(m^3)\) | Multiplex, weighted |
MLMaOP (Pizzuti and Socievole 2017) \(^{e}\) | Direct | Multi-objective Optimization | – | Multiplex |
NFC (Aslak et al. 2018) | Direct | Random walk and Infomap | \(O(m(n+m))\) | Multiplex, temporal |
S2-jNMF (Ma et al. 2018) | Direct | Nonnegative matrix factorization | \(O(rn^2km)\) | Multiplex |
MNLPA (Alimadadi et al. 2019) | Direct | Label Propagation | O(nk) | Multiplex, directed, weighted |
IterModMax (Pamfil et al. 2019) | Direct | SBM and Modularity maxminization | \(O(n^2L)\) | Multiplex, temporal |
Direct | Spectral graph wavelet | \(O(n^2L)\) | Multiplex, temporal | |
CMNC (Chen et al. 2019) | Direct | Tensor Decomposition | \(O(n^3L)\) | Multiplex |
MCD-Berlingerio (Berlingerio et al. 2011a) \(^{f}\) | Flattening | Employing monolayer algorithms | – | Multi-dimensional |
CDHIA (Tang et al. 2012b) | Flattening | network integration and k-means | \(\ge O(nICK)\) | Multi-dimensional |
AggregationPan (Pan et al. 2018) | Flattening | Cutting edges with weight < threshold | \(O((m+n)L)\) | Multiplex, weighted |
ParticleGao (Gao et al. 2019) | Flattening | Particle Competition | \(O(nICL^2)\) | Multiplex, directed, weighted |