基于貢獻(xiàn)函數(shù)的重疊社區(qū)劃分算法

劉功申; 孟魁; 郭弘毅; 蘇波; 李建華

doi:10.11999/JEIT161109

基于貢獻(xiàn)函數(shù)的重疊社區(qū)劃分算法

doi: 10.11999/JEIT161109

基金項(xiàng)目:

國家973關(guān)鍵技術(shù)研究項(xiàng)目(2013CB329603)，國家自然科學(xué)基金(61472248)

計(jì)量
- 文章訪問數(shù): 1270
- HTML全文瀏覽量: 134
- PDF下載量: 410
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2016-10-18
- 修回日期: 2017-04-24
- 刊出日期: 2017-08-19

Overlapping-communities Recognition Algorithm Based on Contribution Function

Funds:

The National 973 Key Basic Research Program of China (2013CB329603), The National Natural Science Foundation of China (61472248)

摘要

摘要: 現(xiàn)實(shí)世界中的網(wǎng)絡(luò)結(jié)構(gòu)呈現(xiàn)出重疊社區(qū)的特征。在研究經(jīng)典的標(biāo)簽算法的基礎(chǔ)上，該文提出基于貢獻(xiàn)函數(shù)的重疊社區(qū)發(fā)現(xiàn)算法。算法將每個(gè)節(jié)點(diǎn)用三元組(閾值、標(biāo)簽、從屬系數(shù))集合來表示。節(jié)點(diǎn)的閾值是每次迭代過程中標(biāo)簽淘汰的依據(jù)，該值由多元線性方程自動(dòng)計(jì)算而來。從屬系數(shù)用于衡量當(dāng)前節(jié)點(diǎn)與標(biāo)簽所標(biāo)識(shí)社區(qū)的相關(guān)度，從屬系數(shù)的值越大說明該節(jié)點(diǎn)與標(biāo)簽所標(biāo)識(shí)社區(qū)的關(guān)聯(lián)性越強(qiáng)。在每一次迭代的過程中，算法依據(jù)貢獻(xiàn)函數(shù)計(jì)算每個(gè)節(jié)點(diǎn)的從屬系數(shù)，并生成新的三元組集合。然后依據(jù)標(biāo)簽決策規(guī)則淘汰標(biāo)簽，進(jìn)行從屬系數(shù)規(guī)范化。通過對(duì)真實(shí)的復(fù)雜網(wǎng)絡(luò)和LFR(Lancichinetti Fortunato Radicchi)自動(dòng)生成的網(wǎng)絡(luò)進(jìn)行測(cè)試可知，該算法的社區(qū)劃分準(zhǔn)確率高，而且劃分結(jié)果穩(wěn)定。
- 復(fù)雜網(wǎng)絡(luò) /
- 社區(qū)發(fā)現(xiàn) /
- 重疊社區(qū)
Abstract: Overlapping is one of the most important characteristics of real-world networks. Based on the classic labeling algorithm, the overlapping-community orientated label propagation algorithm based on contribution function is proposed. In this algorithm, each node is indicated by a set of triples (threshold, label, and coefficient). The threshold value of every node is used as a metric for labels decision, which is calculated automatically by multiple linear regression equation. The dependent coefficient is used to measure the relevance of the current node with the correspondent community which is marked by the label. A greater value of dependent coefficient means a stronger association between the node and the community. During each iteration process, the dependent coefficients are calculated through Contribution Function (CF) of each node, and new triples are produced. Then the labels in terms of decision rules are selected, and the dependent coefficients of the node are normalized. According to the tests with real-world networks and automatic generation of LFR (Lancichinetti Fortunato Radicchi) test network, the algorithm can divide communication with high accuracy and robust result.
- Complex networks /
- Communities detecting /
- Overlapping communities

HTML全文

參考文獻(xiàn)(15)

WANG Xiaofeng, LIU Gongshen, PAN Li, et al. Uncovering fuzzy communities in networks with structural similarity[J]. Neurocomputing, 2016, 210(1): 26-33.

PALLA G, DERENVI I, FARKAS I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818.

LEE C, REID F, McDAID A, et al. Detecting highly overlapping community structure by greedy clique expansion [C]. ACM International Conference on Paper Presented at SNA-KDD Workshop, Washington DC, USA, 2010. arXiv: 1002.1827.

GREGORY S. An algorithm to find overlapping community structure in networks[J]. LNCS, 2007, 4702(12): 91-102.

SHI Xiaohua. Community detection in social network with pair wisely constrained symmetric non-negative matrix factorization[C]. Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Paris, France, 2015: 541-546.

LIU Xiao, WEI Yiming, WANG Jian, et al. Community detection enhancement using no-negative matrix factorization with graph regularization[J]. International Journal of Modern Physics B, 2016, 30(20): 1650130.

WANG Zhaoxian, WANG Wenjun, XUE Guixiang, et al. Semi-supervised community detection framework based on non-negative factorization using individual labels[C], The Sixth International Conference on Swarm Intelligence, Beijing, China, 2015, 349-359

RAGHAVAN U N, ALBERT R, and KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E Statistical Nonlinear Soft Matter Physics, 2007, 76(3 Pt 2):036106.

GREGORY S. Finding overlapping communities in networks by label propagation[J]. New Journal of Physics, 2009, 12(10): 2011-2024.

ULRIK B. A faster algorithm for betweenness centrality[J]. Journal of Mathematical Sociology, 2001, 25(2): 163-177.

EPPSTEIN D and WANG J. Fast approximation of gentrality[J]. Journal of Graph Algorithms and Applications, 2004, 8(1): 39-45.

KLEINBERG J M. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM (JACM), 1999, 46(5): 604-632.

NICOSIA V, MANGIONI G, CARCHIOLO V, et al. Extending the definition of modularity to directed graphs with overlapping communities[J]. Journal of Statistical Mechanics Theory Experiment, 2009, 2009(3): 3166-3168.

LANCICHINETTI A, FORTUNATO S, and RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E Statistical Nonlinear Soft Matter Physics, 2008, 78(2): 046110.

CAO Xiaochun, WANG Xiao, JIN Di, et al. Identifying overlapping communities as well as hubs and outliers via nonnegative matrix factorization[J]. Scientific Reports, 2013, 03: 2993. doi: 10.1038/srep02993.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計(jì)