复杂网络社区结构划分方法
?
復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分方法
?
隨著對(duì)網(wǎng)絡(luò)性質(zhì)的物理意義和數(shù)學(xué)特性的深入研究，人們發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)都具有一個(gè)共同性質(zhì)，即社區(qū)結(jié)構(gòu)。也就是說(shuō)，整個(gè)網(wǎng)絡(luò)是由若干個(gè)“社區(qū)”或“組”構(gòu)成的。每個(gè)社區(qū)內(nèi)部的結(jié)點(diǎn)間的連接相對(duì)非常緊密，但是各個(gè)社區(qū)之間的連接相對(duì)來(lái)說(shuō)卻比較稀疏[1][2]。揭示網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，對(duì)于深入了解網(wǎng)絡(luò)結(jié)構(gòu)與分析網(wǎng)絡(luò)特性是很重要的。如社會(huì)網(wǎng)絡(luò)中的社區(qū)代表根據(jù)興趣和背景而形成的真實(shí)的社會(huì)團(tuán)體；引文網(wǎng)絡(luò)中的社區(qū)代表針對(duì)同一主題的相關(guān)論文；萬(wàn)維網(wǎng)中的社區(qū)就是討論相關(guān)主題的若干網(wǎng)站[3]；而生物化學(xué)網(wǎng)絡(luò)或者電子電路中的網(wǎng)絡(luò)社區(qū)可以是某一類(lèi)功能單元[4][5]。發(fā)現(xiàn)這些網(wǎng)絡(luò)中的社區(qū)有助于我們更加有效的理解和開(kāi)發(fā)這些網(wǎng)絡(luò)。
在復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分的研究中，社區(qū)結(jié)構(gòu)劃分算法所要?jiǎng)澐值木W(wǎng)絡(luò)大致可分為兩類(lèi)，一類(lèi)是比較常見(jiàn)的網(wǎng)絡(luò)，即僅包含正聯(lián)系的網(wǎng)絡(luò)(網(wǎng)絡(luò)中邊的權(quán)值為正實(shí)數(shù))；另一類(lèi)是符號(hào)社會(huì)網(wǎng)絡(luò)，即網(wǎng)絡(luò)中既包含正向聯(lián)系的邊，也包含負(fù)向聯(lián)系的邊。因此劃分網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的算法相應(yīng)分為兩大類(lèi)，而對(duì)于第一類(lèi)網(wǎng)絡(luò)又提出了許多不同的社區(qū)結(jié)構(gòu)劃分算法，劃分第一類(lèi)網(wǎng)絡(luò)社區(qū)的傳統(tǒng)算法可分為兩大類(lèi)，第一類(lèi)是基于圖論的算法，比如K-L算法[6]、譜平分法[7][8]、隨機(jī)游走算法[9]和派系過(guò)濾算法[10][11]等；第二類(lèi)是層次聚類(lèi)算法，比如基于相似度度量的凝聚算法[2]和基于邊介數(shù)度量的分裂算法[1][12][13]等。最近幾年從其他不同的角度又提出了許多劃分第一類(lèi)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的算法，大致可劃分如下：基于電阻網(wǎng)絡(luò)性質(zhì)的算法[14]、基于信息論的算法[15]、基于PCA的算法[16]和最大化模塊度[17]的算法[18-23]等。對(duì)于符號(hào)網(wǎng)絡(luò)，Doreian和Mrvar提出了一種利用局部搜索劃分符號(hào)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的算法[24]，且Bo Yang等提出一種基于代理的啟發(fā)式劃分符號(hào)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的算法(FEC)[25]。
盡管復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問(wèn)題得到了大量的研究，但還存在一些尚未解決的基本問(wèn)題，如社區(qū)概念雖然大量使用，但卻缺少?lài)?yán)格的數(shù)學(xué)定義；大多數(shù)社區(qū)發(fā)現(xiàn)算法雖然性能優(yōu)越，但所需計(jì)算量卻很大。這說(shuō)明復(fù)雜網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)的研究還需要付出大量的努力。
?
轉(zhuǎn)自:http://www.sciencenet.cn/m/user_content.aspx?id=229030
?
參考文獻(xiàn)
[1] Girvan M, Newman M E J. Community structure in social and biological networks[J]. PNAS, 2001, 99(12): 7821-7826.
?
[2]Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133.
?
[3]Fell D A, Wagner A. The small world of metabolism[J]. Nature(Biotechnology, 2000, (18): 1121-1122.
?
[4] Pool l, Kochen M. Contacts and Influence[J]. Social Networks, 1978, (1): 1-48.
?
[5] Milgram S. The small world problem[J]. Psychology Today, 1967, (2): 60-67.
?
[6] Kernighan B W, Lin S. An efficient heuristic procedure for portioning graphs[J]. Bell System Technical Journal, 1970, 49: 291-307.
?
[7] Fiedler M. Algebraic connectivity of graphs[J]. Czechoslovak Mathematical Journal, 1973, 23(98): 298-305.
?
[8]Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphs[J]. SIAM Journal on Matrix Analysis and Applications. 1990, 11(3): 430-452.
?
[9]P. Pons and M. Latapy. Computing Communities in Large Networks Using Random?? Walks[J]. Computer and Information Sciences. 2005,284-293.
?
[10]G. Palla, I. Derenyi, I. Farkas et al. Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society[J]. Nature,2005 435(7043): 814-818.
?
[11]G. Palla, I. Farkas, P. Pollner, I. Derenyi et al. Directed network modules[J]. Phys. New. J, 2007,186.
?
[12]Tyler J, Wilkinson D, Huberman B. Email as spectroscopy: Automated discovery of community structure within organizations[C]. International Conference on Communities and Technologies, 2003, 81-96.
?
[13]F. Radicchi, C. Castellano, F. Cecconi et al. Defining and identifying communities in networks[J]. Eur. Phys. J. B, 2004, 101: 2658-2663.
?
[14]Wu F, Huberman B A. Find communities in linear time: A physics approach[J]. Euro. Phys. J B, 2003, 38: 331-338.
?
[15]Rosvall M, Bergstrom C T. An information-theoretic framework for resolving community structure in complex networks[J]. PNAS, 2007, 104(18): 7327-7331.
?
[16]Chonghui Guo, Liang Zhang. An Analysis Method Based on PCA for the Community Structure in Complex Networks[J]. Operations Research and Management Science, 2008, 17(6), 144-149.
?
[17]Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69 (2): 026113.
?
[18]Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Phys. Rev. E, 2004,70: 066111.
?
[19]Duch J, Arenas A. Community detection in complex networks using extreme optimization[J]. Physical Review E,2005,72: 027104.
?
[20]R. Guimerà and L. A. N. Amaral, Functional cartography of complex metabolic networks[J]. Nature, 2005, 433: 895-900.
?
[21]A. Medus, G. Acu?a, and C. O. Dorso. Detection of community structures in networks via global optimization[J]. Physica A, 2005, 358: 593-604.
?
[22]J. Reichardt and S. Bornholdt. Statistical Mechanics of Community Detection[J]. Phys. Rev. E, 2006, 74: 016110.
?
[23]Newman M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3): 036104.
?
[24]P. Doreian and A. Mrvar. A Partitioning Approach to Structural Balance[J]. Social? Networks, 1996, 18(2): 149-168.
?
[25]Bo Yang, William K. Cheung, and Jiming Liu. Community Mining from Signed Social Networks[J]. IEEE Transactions on Knowledge and Data Engineering. 2007, 19(10): 1333-1348.
?
總結(jié)
以上是生活随笔為你收集整理的复杂网络社区结构划分方法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 核聚类与支持向量聚类
- 下一篇： 复杂系统与复杂网络