基于矢量影響力聚類系數(shù)的高效有向網(wǎng)絡(luò)社團(tuán)劃分算法
doi: 10.11999/JEIT170102
-
1.
(北京郵電大學(xué)網(wǎng)絡(luò)空間安全學(xué)院可信分布式計(jì)算與服務(wù)教育部重點(diǎn)實(shí)驗(yàn)室 北京 100876) ②(北京郵電大學(xué)國(guó)際學(xué)院 北京 100876) ③(北京師范大學(xué)社會(huì)管理研究院 北京 100875)
基金項(xiàng)目:
國(guó)家973 計(jì)劃項(xiàng)目(2013CB 329600)，教育部哲學(xué)社會(huì)科學(xué)重大攻關(guān)項(xiàng)目(15JZD027)，十二五國(guó)家科技支撐計(jì)劃國(guó)家文化科技創(chuàng)新工程2013 年備選項(xiàng)目(2013BAH43F01)
Vector Influence Clustering Coefficient Based Efficient Directed Community Detection Algorithm
-
1.
(Key Laboratory of Trustworthy Distributed Computing and Service of Education Ministry, Beijing University of Posts and Telecommunications, Beijing 100876,China)
-
2.
(International School, Beijing University of Posts and Telecommunications, Beijing 100876, China)
Funds:
The National 973 Project of China (2013CB329600), The Philosophy and Social Science Project of Education Ministry (15JZD027), The National Culture Support Foundation Project of China (2013BAH43F01)
-
摘要: 社團(tuán)結(jié)構(gòu)劃分對(duì)于分析復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特性非常重要，以往研究往往側(cè)重對(duì)無(wú)向網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)挖掘，對(duì)新興的微信朋友圈網(wǎng)絡(luò)、微博關(guān)注網(wǎng)絡(luò)等涉及較少，并且缺乏高效的劃分工具。為解決傳統(tǒng)社團(tuán)劃分算法在大規(guī)模有向社交網(wǎng)絡(luò)上無(wú)精確劃分模擬模型，算法運(yùn)行效率低，精度偏差大的問(wèn)題。該文從構(gòu)成社團(tuán)結(jié)構(gòu)最基礎(chǔ)的三角形極大團(tuán)展開數(shù)學(xué)推導(dǎo)，對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的局部信息傳遞過(guò)程進(jìn)行建模，并引入概率圖有向矢量計(jì)算理論，對(duì)有向社交網(wǎng)絡(luò)中具有較大信息傳遞增益的節(jié)點(diǎn)從數(shù)學(xué)基礎(chǔ)創(chuàng)造性地構(gòu)建了有向傳遞增益系數(shù)(Information Transfer Gain, ITG)。該文以此構(gòu)建了新的有向社團(tuán)結(jié)構(gòu)劃分效果的目標(biāo)函數(shù)，提出了新型有向網(wǎng)絡(luò)社團(tuán)劃分算法ITG，通過(guò)在模擬網(wǎng)絡(luò)數(shù)據(jù)集和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，驗(yàn)證了所提算法的精確性和新穎性，并優(yōu)于FastGN, OSLOM和Infomap等經(jīng)典算法。
-
關(guān)鍵詞:
- 有向社團(tuán)劃分 /
- 信息傳遞增益 /
- 目標(biāo)函數(shù)優(yōu)化 /
- 算法可擴(kuò)展性
Abstract: Community detection method is significant to character statistics of complex network. Community detection in directed structured network is an attractive research problem while most previous approaches attempt to divide undirected networks into communities while there has appeared many large scale directed social network such as WeChat circle of friends and Sina Micro-Blog. To solve the problem that low quality of model, low efficiency of execution and high deviation of precision from the conventional community detection algorithm on large-scale social network and directed network, this paper provides an approach that starts with the triangle structure of community basis and models the local information transfer to detect community in large-scale directed social network. Basing on the directed vector theory in probability graph and the high information transfer gain of vertex in directed network, this paper constructs the Information Transfer Gain (ITG) method and the corresponding target functions for evaluating the quality of a specific partition in community detection algorithm. Then the combine of ITG with the target function to compose the new community detection algorithm for directed network. Extensive experiments in synthetic signed network and real-life large networks derived from online social media, it is proved that the proposed method is more accurate and faster than several traditional community detection methods such as FastGN, OSLOM and Infomap. -
XIE J, KELLEY S, and SZYMANSKI B K. Overlapping community detection in networks: The state-of-the-art and comparative study[J]. ACM Computing Surveys (CSUR), 2013, 45(4): 2-35. doi: 10.1145/2501654.2501657. NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133. doi: 10.1103/PhysRevE.69.066113. CLAUSET A, NEWMAN M E J, and MOORE C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(6): 066111. doi: 10.1103/PhysRevE.70. 066111. BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10): 1-12. doi: 10.1088/1742-5468/2008/10/P10008. PRAT-PREZ A, DOMINGUEZ-SAL D, and LARRIBA- PEY J L. High quality, scalable and parallel community detection for large real graphs[C]. The 23rd International Conference on World Wide Web, ACM, Seoul, Korea 2014: 225-236. doi: 10.1145/2566486.2568010. ZHU X, GHAHRAMANI Z, and LAFFERTY J. Semi- supervised learning using Gaussian fields and harmonic functions[C]. International Conference on Machine Learning, Washington D.C., US, 2003, 3: 912-919. RAGHAVAN U N, ALBERT R, and KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, 2007, 76(3): 036106. doi: 10.1103/PhysRevE.76.036106. PONS P and LATAPY M. Computing communities in large networks using random walks[C]. International Symposium on Computer and Information Sciences. Springer Berlin Heidelberg, Krakow, Poland, 2005: 284-293. doi: 10.1007/ 11569596_31. ROSVALL M and BERGSTROM C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences, 2008, 105(4): 1118-1123. doi: 10.1073/pnas.0706851105. LANCICHINETTI A and FORTUNATO S. Community detection algorithms: A comparative analysis[J]. Physical Review E, 2009, 80(5): 056117. doi: 10.1103/PhysRevE.80. 056117. PALLA G, DERNYI I, FARKAS I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818. doi: 10.1038/nature03607. AHN Y Y, BAGROW J P, and LEHMANN S. Link communities reveal multi scale complexity in networks[J]. Nature, 2010, 466(7307): 761-764. doi: 10.1038/nature09182. LANCICHINETTI A, RADICCHI F, RAMASCO J J, et al. Finding statistically significant communities in networks[J]. PloS One, 2011, 6(4): e18961. doi: 10.1371/journal.pone. 0018961. YANG J and LESKOVEC J. Overlapping community detection at scale: A nonnegative matrix factorization approach[C]. The Sixth ACM International Conference on Web Search and Data Mining. ACM, Rome, Italy, 2013: 587-596. doi: 10.1145/2433396.2433471. NEWMAN M E J and CLAUSET A. Structure and inference in annotated networks[J]. Nature Communications, 2016,7: 11863. doi: 10.1038/ncomms11863. KOLLER D and FRIEDMAN N. Probabilistic Graphical Models: Principles and Techniques[M]. Massachusetts USA, MIT Press, 2009: 1-5. PRAT-PREZ A, DOMINGUEZ-SAL D, BRUNAT J M, et al. Shaping communities out of triangles[C]. The 21st ACM International Conference on Information and Knowledge Management, ACM, 2012: 1677-1681. doi: 10.1145/2396761. 2398496. LEVORATO V and PETERMANN C. Detection of communities in directed networks based on strongly p-connected components[C]. IEEE 2011 International Conference on Computational Aspects of Social Networks (CASoN), Salamanca, Spain, 2011: 211-216. doi: 10.1109/ CASON.2011.6085946. ARENAS A, DUCH J, FERNNDEZ A, et al. Size reduction of complex networks preserving modularity[J]. New Journal of Physics, 2007, 9(6): 1-14. doi: 10.1088/1367-2630/9/6/176. -
計(jì)量
- 文章訪問(wèn)數(shù): 1103
- HTML全文瀏覽量: 133
- PDF下載量: 293
- 被引次數(shù): 0
下載:
