用于社团分析的差异性度量方法*

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

用于社团分析的差异性度量方法*

孙正, 宋文军, 王崇骏** , 谢俊元

出版日期:2015-04-03 发布日期:2015-04-03
作者简介: (计算机软件新技术国家重点实验室, 南京大学计算机科学与技术系, 南京, 210093)
基金资助:
国家自然科学基金( 60503021, 60721002, 60875038) , 江苏省科技支撑计划( BE2009142, BE2010180) , 教育部重点项目( 108151)

Vertex dissimilarity in community discovery

Sun Zheng, Song Wen Jun, Wang Chong Jun, Xie Jun Yuan

Online:2015-04-03 Published:2015-04-03
About author: ( State Key Laboratory for Novel Software T echnology, Department of Computer Science and Technology, Nanjing University, Nanjing, 210093, China)

摘要/Abstract

摘要： 在经典的社团发现算法中, 相似性往往作为聚类方法的标准而存在. 本文从当前社团发现研究的顶点相似性的反面出发, 提出顶点差异性, 并且提出了从顶点自身出发, 从一个顶点出发两种差异
性度量方法; 根据提出的顶点差异性, 应用于当前的常用社团发现算法, 得出结果进行对比分析.

Abstract: Community discovery, which is an important application of data mining in social network analysis, is used to divide the network into distinct groups through detecting the relationship between vertices and edges. Within
these groups there are many connections between vertices, but between groups there are fewer. T his property can reflect the inner structure of the network. Clustering algorithm frequently uses similarity as a standard in its clustering progress. Based on the inverse of
vertex similarity, we put emphasis upon using dissimilarity between vertices to find all the communities in the network. There are also two methods to measure the dissimilarity, respectively based on the vertex itself and the
other vertex in the network. Applying the two kinds of dissimilarity to the classic Girven -Newman algorithm ( GN ), we discover two improved GN algorithms, and in the end, compare results of the two methods according to the current community
discovery algorithms. We show that, in some cases, can greatly improve the efficiency of the our method. Our algorithms are meaningful for the future research on community discovery.

孙正, 宋文军, 王崇骏** , 谢俊元 . 用于社团分析的差异性度量方法*

[J]. 南京大学学报(自然科学版), 2010, 46(5): 528–534.

Sun Zheng, Song Wen Jun, Wang Chong Jun, Xie Jun Yuan
. Vertex dissimilarity in community discovery
[J]. Journal of Nanjing University(Natural Sciences), 2010, 46(5): 528–534.

参考文献

[ 1 ] Michelle G, Newman M E J. Community struc ture in social and biological networks. Proceedings of the Natronal Academy of Sciences of the United States of America, 2002, 99 ( 12) : 7821~ 7826.
[ 2 ] Zhou H. Distance, dissimilarity index, and network community structure. Physical Review E, 2003, 67(6): 061901.
[ 3 ] Zachary W W. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 1977 ( 33 ) : 452~ 473.
[ 4 ] Jean?Baptiste A, Ana ? s B, Christine B, et al. Two local dissimilarity measures for weighted graphs with application to protein interaction networks. Advances in Data Analysis and Classification, 2008, 3~ 16.
[ 5 ] Pons P, Latapy M . Computing communities in large networks using random walks. Journal of Graph Algorithm and Application, 2004, 10: 284~ 293.
[ 6 ] Stanley M . The small world problem. Psychology T oday, 1967, 1: 60~ 67.
[ 7 ] David K, James H K. Network analysis. Beverly Hills: Sage Publication, 1982, 199~ 208.
[ 8 ] Bron C, Kerbosch J. Finding all cliques of an undirected graph. Commnications of the Association for Computing M achinery, 1973, 16( 9): 575~ 577.
[ 9 ] Brandes U. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 2001, 25( 2) : 163~ 177.
[ 10] James P B, Erik M B. Local method for detecting communities. Physical Review E ( Statistical, Nonlinear, and Soft Matter Physics ), 2005, 72( 4) : 046108.
[ 11] Aaron C, Newman M E J, Cristopher M , et al. Finding community structure in very large networks. Physical Review E, 2004, 70 (6) : 066111.
[ 12] Eric D K. Understanding complex networks with community finding algorithms. T ool -Tech Technique Report SURF 2005, 2005.
[ 13] Estrada E, Hatano N. Communicability in complex networks. Physical Review E, 2008, 77 (3) : 036111.
[ 14] Santo F. Community detection in graphs. Physics Reports, 2010, 486( 3- 5): 75~ 174.
[ 15] Steve G. An algorithm to find overlapping community structure in networks. Proceedings of the 11 th European Conference on Principles and Practice of Knowledge Discovery in Databases. Warsaw: Poland Springer, 2007, 9: 91~ 102.
[ 16] Newman M E J, Girvan M. Finding and evaluating community structure in networks. Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, 2004, 69( 2) : 026113.
[ 17] Wu F, Huberman B A. Finding communities in linear time: A physics approach. The European Physical Journal B - Condensed Matter and Complex Systems, 2004, 38(2): 331~ 338.
[ 18] Hu J, Huang H K, Gao F. A clustering algorithm for parallel coordinates?based measure model and its applications. Journal of Nanjing University( Natural Sciences) , 2009, 45 ( 5) :
645~ 655. (胡俊, 黄厚宽, 高芳. 一种基于平行坐标度量模型的聚类算法及其应用. 南京大学学报( 自然科学) , 2009, 45 ( 5) : 645~ 655) .
[ 19] Zheng M M, Ji G L. An improved density based distributed clustering. Journal of Nanjing University( Natural Sciences), 2008, 44 ( 5): 536~ 543. ( 郑苗苗, 吉根林. 一种基于密度的分布式聚类算法. 南京大学学报( 自然科学), 2008, 44 ( 5) : 536~ 543) .

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed