社区挖掘技术研究

J4 ›› 2012, Vol. 34 ›› Issue (9): 154-159.

社区挖掘技术研究

李星，钟志农，景宁，伍勇

（国防科学技术大学电子科学与工程学院，湖南长沙 410073）

收稿日期:2012-04-13 修回日期:2012-06-25 出版日期:2012-09-25 发布日期:2012-09-25
基金资助:
国家863计划资助项目（2011AA120300）；湖南省自然科学基金资助项目（11JJ4028）

Research on Community Detection Method

LI Xing,ZHONG Zhinong,JING Ning,WU Yong

（School of Electronics Science and Engineering,
National University of Defense Technology,Changsha 410073,China）

Received:2012-04-13 Revised:2012-06-25 Online:2012-09-25 Published:2012-09-25

摘要/Abstract

摘要：

复杂网络分析已成为近年来的一个热点研究领域。如何快速有效地对复杂网络进行社区划分，并在社区划分的基础上找出网络中的重要节点有很强的现实意义。本文分析比较了近年来复杂网络分析中社区结构挖掘算法和社区节点等级排序算法的原理和特征，最后对复杂网络分析的发展进行了总结和展望。

关键词: 社区挖掘, 网络分析, 节点重要等级

Abstract:

The complex network analysis is a hot research field.It is very important that how to discover community quickly and find the important vertices in a complex network.In this paper,current research jobsincluding community detection algorithms and vertices sorting algorithms are analyzed and compared.At last,the future work of the complex network analysis is discussed.

Key words: community detection;SNA;vertices ranking

李星，钟志农，景宁，伍勇. 社区挖掘技术研究[J]. J4, 2012, 34(9): 154-159.

LI Xing,ZHONG Zhinong,JING Ning,WU Yong. Research on Community Detection Method[J]. J4, 2012, 34(9): 154-159.

参考文献

［1］Watts D J, Strogatz S H. Collective of Dynamic of ‘Small Word’ Network ［J］.Nature,1998,393(6684):440442.
［2］Wilkinson D M,Huberman B A.A Method for Finding Communities of Related Genes［C］∥Proc of the National Academy of Science,2004：52415248.
［3］Guimera R, Amaral L A N.Functional Cartography of Complex Metabolic Networks［J］.Nature,2005,433:895900.
［4］White S,Smyth P.A Spectral Clustering Approach to Finding Communities in Graph［C］∥Proc of SIAM Data Mining,2005:274285.
［5］Palla G,Derenyi I,Farkas I,et al. Uncovering the Overlapping Community Structures of Complex Networks in Nature and Society［J］. Nature,2005,433:814818.
［6］Girvan M,Newman M E J.Community Structure in Social and Biological Networks［J］.Proceedings of the National Academy of Science,2002,9(12):78217826.
［7］Tyler J R,Wilkinson D M,Huberman B A.Email as Spectroscopy:Automated Discovery of Community Structure within Organizations［C］∥Proc of the 1st International Conference on Communities and Technologies, 2003:8196.
［8］Radicchi F,Castellano C,Cecconi F,et al.Defining and Identifying Communities in Networks［J］.Proceedings of the National Academy of Science,2004,101(9):26582663.
［9］Moussiades L, Vakali A.Mining the Community Structure of a Web Site［C］∥Proc of the 4th Balkan Conference in Informatics,2009:239244.
［10］Newman M E J,Girvan M.Finding and Evaluating Community Structure in Networks［J］.Physical Review E,2004,69(2):026113.
［11］Guimera R,Amaral L A N.Functional Cartography of Complex Metabolic Networks［J］. Nature,2005,433(7028):895900.
［12］何东晓周栩,基于聚类融合的遗传算法［J］.自动化学报,2010,36(8):11601170.
［13］Fortunato S,Barthelemy M.Resolution Limit in Community Detection［J］.Proceedings of the National Academy of Sciences of the United States of America,2007,104(1):3641.
［14］Yang B,Cheng W K,Liu J.Community Mining from Signed Social Networks［J］.IEEE Transactions on Knowledge and Data Engineering,2007,19(10):13331345.
［15］Liu X,Li D Y,Wang S L,et al. Effective Algorithm for Detecting Community Structure in Complex Networks Based on GA and Clustering［C］∥Proc of the 7th International Conference on Computational Science,2007:657664.
［16］Pizzuti C.GAnet: a Genetic Algorithm for Community Detection in Social Networks［C］∥Proc of the 10th International Conference on Parallel Problem Solving from Nature,2008:10811090.
［17］Newman M E J.Fast Algorithm for Detecting Community Structure in Networks［J］. Physical Review E,2004,69(6):066133.
［18］Kernighan B W,Lin S. An Efficient Heuristic Procedure for Partitioning Graphs［J］.Bell System Technical Journal,1970,49(2):291307.
［19］Yang B,Cheng W K,Liu J.Community Mining from Signed Social Networks ［J］.IEEE Transactions on Knowledge and Data Engineering,2007,19(10):13331345.
［20］Yang Bo,Huang Jing,Liu Dayou.MultiAgent Based Decentralized Algorithm for Social Network Community Mining［C］∥Proc of Advances in Social Network Analysis and Mining(ASONAM’09),2009:7882.
［21］Radicchi F,Castellano C,Cecconi F,et al.Defining and Identifying Communities in Networks［J］.Proceedings of the National Academy of Science,2004,101(9):26582663.
［22］江健.社会通信网中的网络化数据挖掘方法研究［R］.北京：装备指挥技术学院，2009.
［23］淦文燕,李德毅. 一种基于数据场的层次聚类方法［J］. 电子学报,2006(2):6872.
［24］苏瑞, 王勇. 数据场理论在互联网络拓扑建模中的应用［J］. 桂林电子科技大学学报，2008,28(6):516518.
［25］Cobetweenness:A Pairwise Notion of Centrality［EB/OL］.［20070921］.http://arxiv.org/abs/0709.3420.
［26］The Pagerank Citation Ranking:Bringing Order to the Web［EB/OL］.［20081228］.http://dbpubs stanford.edulpub/199966.
［27］Newman M E J.Finding Community Structure in Networks Using the Eigenvectors of Matrices［J］.Physical Review E,2006,73(3):036104.
［28］Hagen L W, Kahng A B. New Spectral Methods for Ratio Cut Partitioning and Clustering［J］. IEEE Transactions on CAD of Integrated Circuits and Systems,1992,11(9):10741085.
［29］Shi J, Malik J. Normalized Cuts and Image Segmentation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,1997,22(8):888905.
［30］Ng A Y,Jordan M I,Weiss Y.On Spectral Clustering:Analysis and an Algorithm［C］∥Proc of NIPS,2001:849856.
［31］Ruan J, Zhang W.An Efficient Spectral Algorithm for Network Community Discovery and Its Applications to Biological and Social Networks［C］∥Proc of ICDM’07,2007:643648.

[1]	单辉, 丁成鑫, 赵中英, 周明成, 贾霄生, 李超, . 基于多图卷积神经网络和注意力机制的学术新星预测方法[J]. 计算机工程与科学, 2022, 44(05): 924-932.
[2]	张素琪1，顾军华2，尹君2，郭京津2. 求解最大团问题的混合修复遗传算法及其在社会网络中的应用[J]. 计算机工程与科学, 2016, 38(12): 2551-2559.
[3]	王金辉，贺利坚，张伟,童向荣. 微博中基于用户偏好的信息传播研究 [J]. J4, 2013, 35(3): 140-144.
[4]	刘裕1，周毅书2，王明哲1. 基于SOA建模仿真的云迁移适合度测评方法[J]. J4, 2013, 35(11): 139-145.
[5]	蔡国永，林航. 社会语义网分析技术研究[J]. J4, 2013, 35(1): 88-93.