- 多元化社交。 Twitter、Facebook、Google+、微博等社交媒体的发展极大丰富了人们的日常生活。人们在社交媒体中分享观点、聊天、购物等。 如果仅关注一个社交网络(或网络中特定的一种关系)则可能忽略许多有价值的隐含信息,这很可能导致错误的分析结果。
- 跨行交易。 方便快捷的在线支付方式正逐渐取代传统的现金支付和信用卡,同时也为金融犯罪提供了新的方式。如果仅使用图形模型分析来自单个银行的转账记录,其结果可能不完整。 因此,有必要根据所有可能的交易途径收集数据,获取完整信息。
- 城市交通系统。 现代社会的科技进步丰富了人们日常的交通出行方式,例如公交、地铁、电车、磁悬浮等。 在分析公共交通系统时,应充分考虑各种交通方式的特点,特别是对于某些枢纽站应更加重视解决交通拥堵问题。 当公交线路拥塞时,乘客可能选择地铁,这同样会导致地铁的拥挤。 所以本质上,城市交通系统更像是一个多层网络模型(Multilayer network),如图1显示了成都公交地铁网络。
多层网络模型相关研究有2篇比较经典的综述 (Kivelä et al. 2014; Boccaletti et al. 2014). ,里面提及的两个模型本质上很像,但是Kivela 的模型在层内连边和层间连边的基础上进一步考虑了“切面”(aspect)的概念,虽然信息更立体了,但是处理起来也麻烦了一些,如下图2所示。
\[\mathcal{M}=\left[\begin{array}{cccc} A_{1} & I_{12} & \cdots & I_{1 L} \\ I_{21} & A_{2} & \cdots & I_{2 L} \\ \vdots & \vdots & \ddots & \vdots \\ I_{L 1} & I_{L 2} & \cdots & A_{L} \end{array}\right] \in \mathcal{R}^{N \times N}\]其中,\(A_1,A_2,..., A_L\) 分别表示 \(1, 2,... ,L\) 层的邻接矩阵,\(\mathcal{R}\) 表示实数集合,\(N\) 表示网络中的节点总数,可以通过各层的节点数求和计算,即 \(N=\sum_{1 \leq l \leq L}|V^l|\)。对角线区域的邻接矩阵 \(I_{\alpha\beta}\) 表示各层之间的层间连边,如果用 \(I\) 表示层间连边,那么
\[I=\bigcup_{\alpha,\beta=1,\alpha\neq\beta}^{L}I_{\alpha\beta}\]其中,\(\alpha\) 和 \(\beta\) 表示多层网络中的层(Layer),\(L\) 表示网络的总层数。
常见的社团质量评价指标:
- 模块度(Modularity)[1]:\[Q=\frac{1}{2 m} \sum_{i j}(A_{i j}-\frac{k_i k_j}{2 m}) \delta(C_i, C_j)\]其中,\(m\) 表示网络中的边数,\(k\) 分别表示节点 \(i\) 和节点 \(j\) 的度,\(\delta(C_i,C_j)\) 表示判断节点 \(i\) 和节点 \(j\) 是否在同一社团的克罗内克函数。模块度的取值范围为 [-0.5, 1),通常认为模块度取值在 0.3~ 0.7 之间,划分的社团结构较为明显。
- NMI(Normalized Mutual Information)[2]:
\[\mathrm{NMI}(A,B) = \frac{-2 \sum_{i=1}^{C_A} \sum_{j=1}^{C_B} N_{ij} \log \frac{N_{ij} N}{N_i N_j}}{\sum_{i=1}^{C_A} N_i \log \frac{C_i}{N} + \sum_{j=1}^{C_B} N_j \log \frac{C_j}{N} }\]其中,\(A\) 和 \(B\) 分别表示真实的社团标签以及算法得到的社团发现结果,\(C_A\) 和 \(C_B\) 分别表示 \(A\) 和 \(B\) 的社团个数。\(N_{ij}\) 表示混淆矩阵中的元素,\(N_i\) 和 \(N_j\) 分别表示混淆矩阵中第 \(i\) 行第 \(j\) 列的元素之和。\(N\) 表示网络中节点总数,即混淆矩阵的维度。NMI 的取值范围是 [0,1],如果算法得到的社团划分结果与真实社团标签完全一致,即 \(A=B\), 那么 \(\mathrm{NMI}(A,B)=1\);反之,如果算法得到的社团结果与真实社团标签完全不一致,则 \(\mathrm{NMI}(A,B)=0\)。
多层网络社团划分思路:
- 聚合法:对每层网络分别划分社团,然后进行社团合并。
- 压扁法:将多层网络(多元网络)压扁成加权单层网络,然后利用经典算法进行划分。
- 直接法:直接在多层网络上进行划分。
Name | Classification | Strategy | Network |
---|---|---|---|
PMM (Tang et al. 2009) | Aggregation | Multilayer modularity maximization | Multi-dimensional |
MULTICLUS (Papalexakis et al. 2013) | Aggregation | Minimum description length | Multiplex, bipartite |
GRAPHFUSE (Papalexakis et al. 2013) | Aggregation | Tensor analysis | Multiplex |
ABACUS (Berlingerio et al. 2013) | Aggregation | Multilayer modularity maximization | Multi-dimensional |
DNMF (Jiao et al. 2017) | Aggregation | Nonnegative matrix factorization | Multiplex, temporal |
EMCD (Tagarelli et al. 2017) | Aggregation | Modularity maximization | Multiplex |
Multilink (Mondragon et al. 2018) | Aggregation | Multilink similarity | Multiplex |
M-EMCD* (Mandaglio et al. 2018) | Aggregation | Modularity maximization | Multiplex |
M-Motif (Huang et al. 2019) | Aggregation | Merge partitions across layers | Multilayer |
MEMM (Zhang et al. 2019) | Aggregation | Multilayer edge mixture model | Multiplex |
HSBM (Paez et al. 2019) | Aggregation | Hierarchical SBM and Bayes | Multiplex |
Variational-Bayes (Ali et al. 2019) | Aggregation | SBM and variational Bayes | Multiplex, weighted |
GenLouvain (Jutla et al. 2011) | Direct | Multiplex map equation | Multiplex, temporal |
MultiGA (Amelio and Pizzuti 2014b) | Direct | Genetic representation | Multiplex |
MultiMOGA (Amelio and Pizzuti 2014a) | Direct | Multi-objective optimization | Multiplex |
CLAN (Dabideen et al. 2014) | Direct | Variational label propagation | Multiplex, temporal |
LART (Kuncheva and Montana 2015) | Direct | Random walk | Multiplex |
Multiplex-Infomap (De Domenico et al. 2015a) | Direct | Multiplex map equation | Multiplex |
LocalNCPs (Jeub et al. 2015) | Direct | Local random walk | Multiplex |
BAZZI (Bazzi et al. 2016) | Direct | Multilayer modularity maximization | Multiplex, temporal |
ML-LCD (Interdonato et al. 2017) | Direct | Local objective function maximization | Multiplex |
GN-QMQM (Pramanik et al. 2017) | Direct | Maximum betweenness edges removal | Multiplex |
Louvain-QMQM (Pramanik et al. 2017) | Direct | Modularity optimization | Multiplex, weighted |
MLMaOP (Pizzuti and Socievole 2017) | Direct | Multi-objective Optimization | Multiplex |
NFC (Aslak et al. 2018) | Direct | Random walk and Infomap | Multiplex, temporal |
S2-jNMF (Ma et al. 2018) | Direct | Nonnegative matrix factorization | Multiplex |
MNLPA (Alimadadi et al. 2019) | Direct | Label Propagation | Multiplex, directed, weighted |
IterModMax (Pamfil et al. 2019) | Direct | SBM and Modularity maximization | Multiplex, temporal |
TMSCD (Kuncheva and Montana 2017, 2019) | Direct | Spectral graph wavelet | Multiplex, temporal |
CMNC (Chen et al. 2019) | Direct | Tensor Decomposition | Multiplex |
MCD-Berlingerio (Berlingerio et al. 2011a) | Flattening | Employing monolayer algorithms | Multi-dimensional |
CDHIA (Tang et al. 2012b) | Flattening | network integration and k-means | Multi-dimensional |
AggregationPan (Pan et al. 2018) | Flattening | Cutting edges with weight < threshold | Multiplex, weighted |
ParticleGao (Gao et al. 2019) | Flattening | Particle Competition | Multiplex, directed, weighted |
常用多层网络可视化工具:
- Muxviz,基于R语言实现,可用于层数较多、大规模网络可视化展示,并可拖动不同角度展示效果。https://www.neusncp.com/user/blog?id=80
- Pymnet,基于Python语言实现,小规模多层网络快速展示。https://www.neusncp.com/user/blog?id=356
- Multinetx,绘制简单的demo效果还可以,可附带超邻接矩阵 https://www.neusncp.com/user/blog?id=82。但超邻接矩阵的效果还是推荐使用这个:https://www.neusncp.com/api/matrix
经典数据集:
- London Multiplex Transport Network:https://www.neusncp.com/api/view_dataset?dataset_id=191
- EUAirTransportation: https://www.neusncp.com/api/view_dataset?dataset_id=186
- mammalia-voles-plj-trapping-60 (田鼠诱捕网络): https://www.neusncp.com/api/view_dataset?dataset_id=183
参考文献:
- Newman ME, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E69(2):026113
- Danon L, Diaz-Guilera A, Duch J, Arenas A (2005) Comparing community structure identification. J StatMech Theory Exp 20055(09):P09008
扩展阅读:
Huang X, Chen D, Ren T, et al. A survey of community detection methods in multilayer networks[J]. Data Mining and Knowledge Discovery, 2020: 1-45.
@article{huang2020survey, title={A survey of community detection methods in multilayer networks}, author={Huang, Xinyu and Chen, Dongming and Ren, Tao and Wang, Dongqi}, journal={Data Mining and Knowledge Discovery}, pages={1--45}, year={2020}, publisher={Springer} }