﻿ 基于谱顶层分割的网络社区层次抽取方法
 计算机系统应用  2020, Vol. 29 Issue (1): 220-224 PDF

Extraction of Network Community Hierarchies Based on Spectrum Top-Segmentation
XIONG Ying
Center for Network and Information, Jiangmen Open University, Jiangmen 529000, China
Foundation item: Research Fund for Distant Open Education of Guangdong Province (YJ1613); Technology Research Program of the Ministry of Public Security (2015JSYJC40)
Abstract: The network community hierarchies are defined by heterogeneous of different scales of link density in essence, it is necessary for network community to detect the dynamically changing information during hierarchies division. In view of this, a method of extraction of network community hierarchies based on spectrum top-segmentation is proposed. Firstly, the spectrum top-segmentation is defined as a dichotomy of subnetwork that no any top-level community can cross two parts, and an expected division top-level segmentation is presented. Then, the queue and link-density are introduced to decompose network, and an algorithm of network community levels extraction is presented. The simulation result shows that the performance of proposed method is better than that of synchronization and multi-scale in stochastic hierarchical networks, and the method is applicated in Email real-world network effectively.
Key words: spectrum top-segmentation     network community     extraction of hierarchies     expected division

1 谱顶层分割 1.1 顶层分割

 图 1 具有网络组织结构的顶层分割

1.2 谱顶层期望划分

 $\begin{gathered} Q\left( {{p_1}} \right) = {m_1} \times {m_2} \times {p_0} - \frac{{{{\left( {{k_1} + {k_2}} \right)}^2} + k_3^2}}{{2M}} \\ Q\left( {{p_2}} \right) = {m_1} \times {m_3} \times {p_1} - \frac{{{{\left( {{k_1} + {k_3}} \right)}^2} + k_2^2}}{{2M}} \\ Q\left( {{p_2}} \right) = {m_1} \times {m_3} \times {p_1} - \frac{{{{\left( {{k_1} + {k_3}} \right)}^2} + k_2^2}}{{2M}} \\ \end{gathered}$ (1)

2 网络层次社区抽取 2.1 连接密度计算

 $\delta _{\rm{0}}^{\rm{*}} = \frac{{\left| {E\left( {\rm {N_1},{N_2}} \right)} \right|}}{{\left| {\rm {N_1}} \right| \times \left| {\rm {N_2}} \right|}}$ (2)

 $\delta _{0}^{*} = \frac{{\delta _{0}^{*} \times n + {\delta _{1}}}}{n + 1}$ (3)

2.2 算法实现

1) initialize q_curr, q_work, q_next

2) N→q_curr, h=0 //N表示整个网络

3) while q_curr is not empty do

4) 　while q_curr is not empty do

5) 　　N←q_curr,d=0

6) 　　　 v=subspaceMethod (N, N1, N2, δ1, d)

7) 　　　if v>0 then //N未被分解

8) 　　　　N1q_work, N2q_work, δ*=δ1

9) 　　　end if

10) 　　　while q_work is not empty do

11) N←q_work and v=subspaceMethod (N, N1, N2, δ1, d)

12) 　　　　if v<=0 then N→q_next

13) 　　　　else if $\scriptstyle{\delta ^*} < = \beta \times {\delta ^*}$ //β确定一个划分是否属于下一个层次

14) 　　　　N1q_work, N2q_work update δ*

15) 　　　　 d=d+1, compute(Q)//计算期望划分值

16) 　　　　else N→q_next //N为最顶层社区

17) 　　　　end if

18) 　　　end if

19) 　　end while

20) 　　end while

21) 　 h=h+1

22) 　if q_next is not empty then output the communities at h level from qnext //返回新的层次社区

23) 　 q_next $\Rightarrow$ q_curr

24) 　end if

25) 　end while

3 实验分析

3.1 同质层次随机网络性能

 图 2 本文方法在层次随机网络的凝聚性精度

3.2 异质层次随机网络性能

 图 3 层次随机网络的凝聚性比较

 图 4 异质随机网络的社区层次抽取结果

4 结论与展望

 图 5 本文方法与同步法和多尺度法的规范化互信息比较

 [1] Diwadkar A, Vaidya U. Synchronization in large-scale nonlinear network systems with uncertain links. Automatica, 2019, 100: 194-199. DOI:10.1016/j.automatica.2018.06.002 [2] Arab M, Afsharchi M. Community detection in social networks using hybrid merging of sub-communities. Journal of Network and Computer Applications, 2014, 40: 73-84. DOI:10.1016/j.jnca.2013.08.008 [3] 赵建军, 汪清, 由磊, 等. 基于信息传递和峰值聚类的自适应社区发现算法. 重庆大学学报, 2018, 41(11): 76-83. [4] Li XM, Xu GQ, Tang MH. Community detection for multi-layer social network based on local random walk. Journal of Visual Communication and Image Representation, 2018, 57: 91-98. DOI:10.1016/j.jvcir.2018.10.003 [5] Mondal SA. An improved approximation algorithm for hierarchical clustering. Pattern Recognition Letters, 2018, 104: 23-28. DOI:10.1016/j.patrec.2018.01.015 [6] Everitt B. Cluster analysis. Quality and Quantity, 1980, 14(1): 75-100. DOI:10.1007/BF00154794 [7] Clauset A, Moore C, Newman MEJ. Hierarchical structure and the prediction of missing links in networks. Nature, 2008, 453(7191): 98-101. DOI:10.1038/nature06830 [8] 张虎, 吴永科, 杨陟卓, 等. 基于多层节点相似度的社区发现方法. 计算机科学, 2018, 45(1): 216-222. DOI:10.11896/j.issn.1002-137X.2018.01.038 [9] Liang X, Du JB. Concurrent multi-scale and multi-material topological optimization of vibro-acoustic structures. Computer Methods in Applied Mechanics and Engineering, 2019, 349: 117-148. DOI:10.1016/j.cma.2019.02.010 [10] Arenas A, Díaz-Guilera A, Pérez-Vicente CJ. Synchronization reveals topological scales in complex networks. Physical Review Letters, 2006, 96(11): 114102. DOI:10.1103/PhysRevLett.96.114102 [11] http://www.urv.cat/en/about/directory/institutional/. [2017-07-01]. [12] Lacerda J, Freitas C, Macau E. Multistable remote synchronization in a star-like network of non-identical oscillators. Applied Mathematical Modelling, 2019, 69: 453-465. DOI:10.1016/j.apm.2018.12.026 [13] Arjmand D, Engblom S, Kreiss G. Temporal upscaling in micromagnetism via heterogeneous multiscale methods. Journal of Computational and Applied Mathematics, 2019, 345: 99-113. DOI:10.1016/j.cam.2018.05.059 [14] 王益文. 复杂网络节点影响力模型及其应用[博士学位论文]. 杭州: 浙江大学, 2015.