多层网络社团发现(Community detection in multilayer networks)

hxy    2020-11-10 16:07

        社团结构(Community structure)在现实世界的复杂系统中普遍存在,对社团结构的分析和挖掘也是复杂网络领域最基础的研究之一。目前,社团发现(Community detection)相关研究大多基于图模型(Graph model)展开,随着网络规模的增加以及网络的多元化发展,传统方法可能由于网络模型的局限导致不正确或不完整的研究结果,如以下场景:
  1. 多元化社交。 Twitter、Facebook、Google+、微博等社交媒体的发展极大丰富了人们的日常生活。人们在社交媒体中分享观点、聊天、购物等。  如果仅关注一个社交网络(或网络中特定的一种关系)则可能忽略许多有价值的隐含信息,这很可能导致错误的分析结果。
  2. 跨行交易。 方便快捷的在线支付方式正​​逐渐取代传统的现金支付和信用卡,同时也为金融犯罪提供了新的方式。如果仅使用图形模型分析来自单个银行的转账记录,其结果可能不完整。 因此,有必要根据所有可能的交易途径收集数据,获取完整信息。
  3. 城市交通系统。 现代社会的科技进步丰富了人们日常的交通出行方式,例如公交、地铁、电车、磁悬浮等。 在分析公共交通系统时,应充分考虑各种交通方式的特点,特别是对于某些枢纽站应更加重视解决交通拥堵问题。 当公交线路拥塞时,乘客可能选择地铁,这同样会导致地铁的拥挤。 所以本质上,城市交通系统更像是一个多层网络模型(Multilayer network),如图1显示了成都公交地铁网络。
Fig.1  成都公交地铁网络

        多层网络模型相关研究有2篇比较经典的综述 (Kivelä et al. 2014; Boccaletti et al. 2014). ,里面提及的两个模型本质上很像,但是Kivela 的模型在层内连边和层间连边的基础上进一步考虑了“切面”(aspect)的概念,虽然信息更立体了,但是处理起来也麻烦了一些,如下图2所示。
Fig.2  Kivela的多层网络模型
因此,Boccaletti等关注的多层网络模型则相对简单,如下图3展示了一个三层网络,实线为层内连边,虚线为层间连边。
Fig.3  Boccaletti关注的多层网络模型
而通常超邻接矩阵可以表示为:
\[\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\) 表示网络的总层数。

常见的社团质量评价指标:
  1. 模块度(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 之间,划分的社团结构较为明显。
  2. 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\)

多层网络社团划分思路:
  1. 聚合法:对每层网络分别划分社团,然后进行社团合并。
  2. 压扁法:将多层网络(多元网络)压扁成加权单层网络,然后利用经典算法进行划分。
  3. 直接法:直接在多层网络上进行划分。
目前的多层网络社团发现算法简单比较如下:
 
Table.1  多层网络社团发现算法总结
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 20172019) 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



常用多层网络可视化工具
  1. Muxviz,基于R语言实现,可用于层数较多、大规模网络可视化展示,并可拖动不同角度展示效果。https://www.neusncp.com/user/blog?id=80
  2. Pymnet,基于Python语言实现,小规模多层网络快速展示。https://www.neusncp.com/user/blog?id=356
  3. Multinetx,绘制简单的demo效果还可以,可附带超邻接矩阵 https://www.neusncp.com/user/blog?id=82。但超邻接矩阵的效果还是推荐使用这个:https://www.neusncp.com/api/matrix

经典数据集:
  1. ​​​​​London Multiplex Transport Network:https://www.neusncp.com/api/view_dataset?dataset_id=191
  2. EUAirTransportation: https://www.neusncp.com/api/view_dataset?dataset_id=186
  3. mammalia-voles-plj-trapping-60 (田鼠诱捕网络): https://www.neusncp.com/api/view_dataset?dataset_id=183


参考文献:
  1. Newman ME, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E69(2):026113
  2. 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}
}
Last Modified: 2020-11-10 20:16
Views: 2.3K

[[total]] comments

Post your comment
  1. [[item.time]]
    [[item.user.username]] [[item.floor]]Floor
  2. Click to load more...
  3. Post your comment