基于社团为粒度的网络分割方法 * )

南京大学学报(自然科学版) ›› 2010, Vol. 46 ›› Issue (5): 511–519.

基于社团为粒度的网络分割方法 *
)

何富贵** , 张燕平, 张铃

出版日期:2015-04-02 发布日期:2015-04-02
作者简介: ( 安徽大学计算机科学与技术学院, 计算智能与信号处理教育部重点实验室, 合肥, 230039
基金资助:
国家自然科学基金( 60675031) , 973!计划 ( 2007CB311003) , 博士后科学基金( 20070411028) , 安徽省自然科学
基金 ( KJ2010B219), 安徽大学 211!工程学术创新团队资助项目

A community partition method for network based on granularity

H eFu Gui , Zhang Yan Ping, Zhang Ling

Online:2015-04-02 Published:2015-04-02
About author: ( School of Computer Science and Technology, Key Laboratory of Intelligent Computing and Signal Processing, Anhui University, Hefei, 230039, China)

摘要/Abstract

摘要： 针对大规模网络的网络分析, 本文提出基于社团为粒度的网络分割方法, 以模块度作为评价准则, 以节点网络属性作为启发式信息对网络进行分割, 使得子图规模相当且具有社团群聚特征. 社团
子图规模相当使得经典的图论算法(如最短路径算法) 充分发挥其作用; 社团子图具有社团结构, 使得子图之间连接边少, 便于粒度分析. 通过美国不同规模的城市交通网络的实验, 证明了基于社团为粒度的
网络分割的实用性, 使得社团子网规模和社团子网数目都适合于经典最短路径算法.

Abstract: Due to large space demanding and time -consuming, the classic graph theory algorithms aren- t suitable for solving some problems in the large -scale network. Most large -scale networks show community structure in the
field of complex network. Sub-graphs of vertices have a higher density of edges within them while a lower density of edges between sub-graphs. Granular Computing imitates the human-s thought of solving complex problems and
granularity decomposition method is a good approach to simplify complex and large -scale problem. To solve large scale network analysis, a community partition method of network based on granularity was proposed. By modularity
for the evaluation criteria and network properties of node for heuristic information, it makes sub -graph scale similar and sub -graph with community structure. Due to sub -graph scale similar and small, the proposed method is
beneficial effect on the classic graph theory algorithms ( such as the shortest path algorithm) of network analysis. Owe to sub -graph with community structure, less connected edges among sub-graph is favorable for granular
computing method. In U. S. city transportation networks of different scale, the result of experiments shows that the proposed method is effective.

何富贵** , 张燕平, 张铃
. 基于社团为粒度的网络分割方法 *
)[J]. 南京大学学报(自然科学版), 2010, 46(5): 511–519.

H eFu Gui , Zhang Yan Ping, Zhang Ling . A community partition method for network based on granularity

[J]. Journal of Nanjing University(Natural Sciences), 2010, 46(5): 511–519.

参考文献

[ 1 ] Zadeh L A. T oward a theory of fuzzy informa tion granulation and its centrality in human rea soning and fuzzy logic. Fuzzy Sets and Systems. 1997, 90(2): 111~ 127.
[ 2 ] Zhang L, Zhang B. T he theory and applications of problem solving ?quotient space based granular computing. The 2 nd Version. Beijing: Tsinghua University Press, 2007, 1~ 105. ( 张 ? 铃,
张钹. 问题求解理论及应用∀ ∀∀ 商空间粒度计算理论及应用. 第 2 版. 北京: 清华大学出版社, 2007, 1~ 105) .
[ 3 ] Lin T Y. Mining associations by linear inequalities. Proceedings of International Conference on Data Mining. Washington: IEEE Computer Society, 2004, 154~ 161.
[ 4 ] Lin T Y. Granular computing: Fuzzy logic and rough sets. Zadeh L A, Kacprzyk J. Computing with words in information/intelligent systems. Physica-Verlag ( A Springer ?Verlag Company) , 1999, 183~ 200.
[ 5 ] Yao Y Y, Liau C J, Zhong N. Granular computing based on rough sets, quotient space theory, and belief functions. Proceedings of the 14 th International Symposium on Methodologies for Intelligent Systems ( ISM IS? 03) , Germany,
Springer: Lecture Notes in Computer Science, 2003, 152~ 159.
[ 6 ] Pawlak Z. Rough sets theoretical aspects of rea soning about data. Dordrecht, Boston, London: Kluwer Academic Publishers, 1991, 1~ 252.
[ 7 ] Zhang L, Zhang B. The quotient space theory of problem solving. Fundamenta Informatcae, 2004, 59: 287~ 298.
[ 8 ] Zhang L, Zhang B. Theory of fuzzy quotient space ( methods of fuzzy granular computing) . Journal of Software, 2003, 14( 4): 770~ 776. ( 张铃, 张钹, 模糊商空间理论. 软件学报2003, 14(4): 770~ 776) .
[ 9 ] Zhang Y P, Zhang L, Wu T . The representation of different granular worlds: A quotient space. Chinese Journal of Computers, 2004, 3:
328~ 333. ( 张燕平, 张? 铃, 吴? 涛. 不同粒度世界的描述法∀ ∀∀ 商空间法. 计算机学报 2004(3) : 328~ 333).
[ 10] Hu J, Wang G Y. Hierarchical model of covering granular space. Journal of Nanjing University ( Natural Sciences) , 2008, 44(5): 551~ 558.
(胡军, 王国胤. 覆盖粒度空间的层次模型. 南京大学学报( 自然科学) , 2008, 44( 5) : 551~ 558) .
[ 11] Watts D J, Strogatz S H. Collective dynamics of small world networks. Nature, 1998, 393 (4): 440~ 442.
[ 12] Barab?si A L, Albert R. Emergence of scaling in random networks. Science, 1999, 286 (5439) : 509~ 512.
[ 13] Borgs C, Chayes J, M ahdian M , et al. Exploring the community structure of news groups. Kim W, Kohavi R, Gehrke J, et al. Proceedings of the 10 th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining. Seattle: AAAI, 2004, 783~ 787.
[ 14] Girvan M, Newman M E J. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99 ( 12): 7821~ 7826.
[ 15] Newman M E J, Girvan M. Finding and evaluating community structure in networks. Physical Review E, 2004, 69(2): 026113.
[ 16] Newman M E J. Modularity and community structure in networks. Proceedings of the National Academy of Sciences of the United States of America, 2006, 103(23) : 8577~ 8582.
[ 17] Wang L, Dai G Z. Community finding in complex networks: Theory and applications. Science and Technology Review, 2005, 23 ( 8): 62~ 66.
[ 18] Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphs. Journal on Matrix Analysis and Applications, 1990, 11( 3) : 430~ 452.
[ 19] Wildinson D, Huberman B A. A method forfinding communities of related genes. Proceedings of the National Academy of Sciences of the U nited States of America, 2004, 11: 5241~ 5248.
[ 20] T yler J R, Wilkinson D M, Huberman B A. Email as spectroscopy: Automate discovery of community structure within organizations. Communities and T echnologies, 2003, 81~ 96.
[ 21] Arenas A, Danon L, Diaz?Guilera A, et al. Community analysis in social networks. T he European Physical Journal B, 2004, 38( 2) : 373~ 380.
[ 22] Radicchi F, Castellano C, Cecconi F, et al. De fining and identifying communities in networks. Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(9): 2658~ 2663.
[ 23] Fortunato S, Latora V, Marchiori M. A method for finding community structure based on information centrality. Physical Review E, 2004, 70: 056104.
[ 24] Newman M E J, Girvan M. Finding and evalua ting community structure in networks. Physical Review E, 2004, 69: 026113
[ 25] Ulrik B, Daniel D, Marco G, et al. On modularity clustering. IEEE Transactions on Knowlegde Data Engineering, 2007, 20 ( 2 ): 172~ 188.
[ 26] Cafieri S, Hansen P. Edge ratio and community structure in networks. Physical Review E, 2010, 81( 2) : 026105.
[ 27] Muff S, Rao F, Caflisch A. Local modularity measure for network clusterizations. Physical Reviews E, 2005, 72(5) : 056107.
[ 28] Fortunato S, Barthelemy M. Resolution limit in community detection. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(1): 36~ 41.
[ 29] Zhuge H, Zhang J S. Topological centrality and its applications. CoRR abs/ 0902!1911. 2009. http: // arxiv. org/ abs/ 0902 ! 1911v1. 2010- 07 - 15.
[ 30] Gan W Y, He N, Li D Y, et al. Community discovery method in networks based on topological potential. Journal of Software, 2009, 20 (8): 2241~ 2254. ( 淦文燕, 赫南, 李德毅等.
一种基于拓扑势的网络社区发现方法. 软件学报, 2009, 20(8): 2241~ 2254) .

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed