摘要
近年来,在不同领域、广泛多样的系统中,图变成了一种极其有用的描述工具,生物,社会,技术和信息网络等许多领域的系统都能建模为图(网络)来研究。为了理解网络系统的特征,网络分析研究就变得非常重要。对网络的研究从最初的规则网络,到随机网络,到近几年的复杂网络,越来越多关于网络的研究工作持续开展。无标度网络的发现,使人类对于复杂网络系统有了全新的认识。在这样的网络中,顶点度的分布显示出很大的不均匀性,同时,表现出高水平的秩序和组织,特点是网络中顶点度的分布非常广泛,大量低度数的顶点围绕少量高度数的顶点共存,网络呈现出社区结构(也称为簇或模块)。
社区发现在社会学、生物学和计算机科学等学科中都有重要应用,如提高网络服务质量、增强网络销售、发现有共同兴趣的科学家小组、揭示政府组织运行方式、发现动物的社会组织结构、聚类功能基因等等。
近年,关于社区发现的很多新概念和新方法被提出来。在无权图研究方面：模块度的提出极大促进该方向的研究,基于模块度优化的社区发现方法成为了主流方法,但现有模块度定义在一些应用背景下存在不足,有的模块度优化方法也存在缺陷。在带权图研究方面：针对带权图的工作相对来说比较少,权值本身的意义没有获得重视。而且,很多社会网络是基于交互行为建立的,交互的数量对社区结构有重要的影响。鉴于上述问题,为扩展社区发现算法的适应范围、提高发现社区的准确性、合理发现带权图中的社区结构,本文关注连接的度量问题,在模块度定义、改进社区发现算法、带权图社区发现等方面开展了研究工作。
本文的主要研究内容和创新之处总结如下：
(1)提出了基于耦合度的模块度。针对现有模块度在社区规模差异大和多社区情况下的不足,根据社区内部顶点间的连接相对紧密,社区之间的连接相对稀疏的特点。定义了社区间的连接密度和社区内的连接密度两个数值,通过二者之比定义了社区间祸合度,社区间连接越稀疏,社区内部越紧密,则社区耦合度越小。基于社区耦合度的定义,提出一种新的基于社区耦合程度的模块度,用来度量整个网络中社区划分质量。通过实验证实,该模块度既适用于社区大小相似的情形,也适用于社区大小差异较大的情形,并且在多社区的情况下,有比较合理的度量效果。
(2)提出了一个非递归分裂的模块度优化社区发现算法。因递归二分过程的影响,分裂式模块度优化算法在多社区情况下存在划分结果可能不理想的问题。本文依据类似于k-均值聚类的思想,提出了一种基于模块度优化的社区发现算法。该算法根据指定的社区数目对网络进行初始划分,通过迭代移动社区内的顶点,完成网络的自组织,使得算法在当前社区数目已定的条件下,搜索到具有最大模块度的网络划分。随后,增大社区数目,重复上述过程,直至模块度减小或社区数目达到用户指定的最大数目k。算法中,每次对社区数目为n的初始划分都是在原始网络上进行,有效避免了递归二分引起的问题。实验表明,社区发现的效果良好。
(3)基于成员交互行为,提出交互度的概念,并应用于层次凝聚社区发现算法。在描述交互关系的社会网络中,直观地认识到,顶点之间交互的强弱主要是包括两个方面：一是交互的绝对数量,二是交互的对等性。据此,提出了顶点交互度的概念,分析了网络拓扑结构对交互度的影响,引入概率中的可靠性概念,把顶点之间的交互度推广到社区之间的交互度。随后,以交互度作为层次凝聚算法的相似度指标,提出了基于交互度的层次凝聚社区发现算法,该算法能够比较自然地模拟社区的形成。实验表明,在带权图中能较好的发现合理的社区结构。
(4)开发了一个社区发现的可视化工具软件Snviewer,提出了分层力导引算法。为了直观、高效地观察图和社区发现结果,基于JAVA平台,利用OpenGL图形编程接口,以力导引方法为布点算法,开发了一个可以动态演示图结构和社区发现结果的可视化工具。为了更好地显示社区发现结果,提出了分层力导引算法。另外,在动态布局过程中提供了人机交互机制,可以直观地人工干预布点过程,使布点结果更符合人们的观察习惯。
In the20th century, graphs have already become extremely useful as the representation of a wide variety of systems in different areas. Biological, social, technological, and information networks can be studied as graphs, and graph analysis has become crucial to understand the features of these systems. More and more study work is being developed further from regular networks to random networks to complex networks, among which, the discovery of scale-free networks gives a fresh view to understand the complex networks. The degree distribute of vertices unevenly in it, meanwhile, it shows a high level of order and organization. The degree distribution is broad, with a tail that often follows a power law:many vertices with low degree coexist with some vertices with large degree. The feature is called community structure.
Community detection plays an important part in the field of sociology, biology and computer science, such as improving quality of service of the World Wide Web, enhancing network sale, finding a group of scientists'interest in common, revealing the secret of government organization running, discovering social structure in animal world, clustering features gene and so forth.
In recent years, a large number of new concept and methods has been given to study community detection. In terms of unweighted graphs, modularity makes the study go further and community detecting algorithms based on modularity optimization has been a mainstream. However, the existing modularity definition is inadequate to all situations and there are still some defects about some algorithms based on modularity optimization. In the study of weighted graphs, there are a few relative studies and the weight's significance be neglected. Lots of social networks are created on interaction activities. Meanwhile, the quantity of such activities is another influence to community structure. Based on these problems, this thesis concerns about the problem of link measure and gives a new research in aspects of modularity definition, improving algorithms based on modularity optimization, community detecting in weighed graphs so as to extend suitable range of the modularity, improve accuracy of community detection, and reveal reasonable community structure of weighted graphs.
The main contributions and novelties of this thesis are summarized as follows:
(1) Proposes a new modularity based on the concept of coupling coefficient. The existing modularity has shortages to compare the quality of the community structure of networks which are very different in size or have multiple communities. According to the characteristic of communities, which vertices are densely connected within the community and have much sparser connection between the communities, it defines values of the link density between communities and the link density within a community. By the ratio of two values, it defines coupling coefficient between communities. The lower the link density between communities is and the higher the link density within community is, the smaller coupling coefficient of community will be. A new modularity based on coupling coefficient is suggested to access the goodness of a network partition.. The experiment figure shows that the new modularity is suitable for both similar and very different communities in size, it also works in multiple community.
(2) Propose a non-recursive and divisive algorithm of modularity optimization for community detecting. For the impact of recursive bisectioning, the divisive algorithm based on modularity optimization is inadequate for multiple communities. Based on k-means clustering idea, the writer suggests a modularity-based algorithm for community detecting. The main idea of our algorithm is setting a number as the number of communities in a network, dividing nodes according to their degree in the network to get initial communities, and optimizing communities by shifting nodes between communities so that modularity has the maximal increase; then changing the number of communities and repeat the process above until the modularity cannot be improved any more by the procedure or the number of communities is changed to k, which is the user-specified biggest number of community. For the initial partition to each number of community works on the original networks, our algorithm avoids the problem caused by recursive bisectioning. The experimental results show that our algorithm can correctly detect the communities.
(3) Propose the concept of interaction degree on the interactive behavior between members of community, and applied to the hierarchical agglomerative algorithm for community detecting. In the social networks representing interactive relationships, it is intuitively realized that the measure of interactive relationships should consider two aspects, one is absolute quantity of interactive activities, and the other is reciprocity of interaction. Accordingly, we propose the concept of interaction degree between vertices and analyze the impact of topology structure of networks on the interaction degree. By introducing the reliability in the probability theory, we extend the interaction degree from between vertices to between communities. Then the interaction degree being as similarity measures, the writer proposes the hierarchical agglomerative algorithm for community detecting. The algorithm can naturally simulate the formation of community. Experiments show that it can detect the reasonable community structure in weighted graphs.
(4) Develop a software tool for visualization of community detection, and propose a layered force-directed algorithm. Basing on JAVA, OpenGL graph programming interface, and force-directed method, we develop a visualization tool for showing dynamically graph structure and community detection consequence so as to make the graph be intuitive. In order to better display the results of community detecting, we propose a layered force-directed algorithm. In addition, it offers human-computer interaction mechanism in dynamic layout process, which makes artificial intervention possible and satisfies operators'observation convention as well.
引文
属性不符
[Adamcsek2006] B. Adamcsek, G. Palla, I.J. Farkas, I. Derenyi, T. Vicsek. Cfmder:Locating cliques and overlapping modules in biological networks[J]. Bioinformatics.2006,22(8):1021_1023.
[Agrawal 1994] R. Agrawal, H.V. Jagadish. Algorithms for searching massive graphs [J], Knowl. Data Eng.1994,6 (2):225-238.
[Agarwa12008] G. Agarwal, D. Kempe. Modularity-maximizing network communities via mathematical programming [J]. Eur. Phys. J. B.2008,66:409-418.
[Ahujal993] R.K. Ahuja, T.L. Magnanti, J.B. Orlin. Network Flows:Theory, Algorithms, and Applications [M]. Englewood Cliffs, USA:Prentice Hall,1993.
[Albert2002] R. Albert. A.-L. Barabasi. Statistical mechanics of complex networks [J]. Rev. Mod. Phys.2002,74 (1):47-97.
[Arenas2007] A. Arenas..1. Duch, A. Fernandez, S. Gomez. Size reduction of complex networks preserving modularity [J]. New Journal of Physics.2007,9:176
[Barabasi1999] AL. Barabasi, Reka Albert. Emergence of Scaling in Random Networks [J]. Science.1999. 286(5439):509-512
[Barber2008] M.J. Barber, M. Faria, L. Streit, O. Strogan. Searching for communities in bipartite networks [J]. in: American Institute of Physics Conference Series, American Institute of Physics, Melville, USA,2008,1021: 171-182.
[Berry2011] J. W. Berry, B. Hendrickson, R. A. Laviolette, C. A. Phillips. Tolerating the Community Detection Resolution Limit with Edge Weighting [J]. Physical Review E.2011,83(5):056119
[Blondel2008] V.D. Blondel, J.-L. Guillaume, R. Lambiotte, E. Lefebvre. Fast unfolding of communities in large networks [J]. J. Stat. Mech.2008,10008
[Boccaletti2006] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.U. Hwang. Complex networks:Structure and dynamics [J]. Phys. Rep.2006,424 (4-5):175-308.
[Bollobas1998] B. Bollobas. Modern Graph Theory [MJ. New York, USA:Springer,1998.
[Brandes2006] U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikolski, D. Wagner. On modularity_np-completeness and beyond. URL http://digbib.ubka.uni-karlsruhe.de/volltexte/documents/3255.
[Bullmore2009] E. Bullmore, O. Sporns. Complex brain networks:graph theoretical analysis of structural and functional systems [J]. Nature Reviews Neuroscience.2009,10(3):186-198
[Burt1976]R.S. Burt. Positions in networks [J], Soc. Forces.1976,55:93-122.
[Chandral989] A.K. Chandra, P. Raghavan, W.L. Ruzzo, R. Smolensky. The electrical resistance of a graph captures its commute and cover times[C]. Proceedings of the twenty-first annual ACM symposium on Theory of computing, ACM, New York, NY, USA,1989:574-586.
[Chen2008]W.Y.C. Chen, A.W.M. Dress, W.Q. Yu. Community structures of networks [J]. Math. Comput. Sci.2008, 1 (3):441-457.
[Clauset2004] A. Clauset, M. E. J. Newman, C. Moore. Finding community structure in very large networks[J]. Physical Review E,2004,70(6):066111.
[Coleman 1964] J.S. Coleman. An Introduction to Mathematical Sociology [M]. London, UK:Collier-Macmillan, 1964.
[Corpetl988]F. Corpet. Multiple sequence alignment with hierarchical clustering[J]. Nucleic Acids Research.1988, 16(22):10881-10890
[Derenyi2005] I. Derenyi, G. Palla. T. Vicsek. Clique percolation in random networks [J]. Phys. Rev. Lett.2005,94 (16):160202.
[Dorogovtsev2002] S.N. Dorogovtsev, J.F.F. Mendes. Evolution of networks [J]. Adv. Phys.2002,51:1079-1187.
[Dourisboure2007] Y. Dourisboure, F. Geraci, M. Pellegrini. Extraction and classification of dense communities in the web [C], Proceedings of the 16th International Conference on the World Wide Web, ACM, New York, NY, USA, 2007,461-470.
[Duch 2005] J. Duch, A. Arenas. Community detection in complex networks using external optimization [J]. Physical Review E,2005,72(2):027104.
[Eades1984] P. Eades. A heuristic for graph drawing [J]. Congressus Nutnerantiunt.1984,42:149-160
[Elias1956] P. Elias. A. Feinstein, C.E. Shannon. Note on maximum flow through a network [J], IRE Trans. Inf. Theory IT-2 (1956):117-119.
[Erdos1959] P. Erdos, A. Renyi. On random graphs. I. Publ. Math.1959, Debrecen 6:290_297.
[Estrada2008] E. Estrada, N. Hatano. Communicability in complex networks [J]. Phys. Rev.2008.77 (3):036111.
[Estrada2009] E. Estrada. N. Hatano. Communicability graph and community structures in complex networks [J]. Appl. Math. Comput.2009.214:500-511
[Flake2002] GW. Flake, S. Lawrence, C. Lee Giles, F.M. Coetzee. Self-organization and identification of web communities [J]. IEEE Computer, 2002,35:66-71.
[Fortunato2010] S. Fortunato. Community detection in graphs [J]. Physics Reports.2010,486:75-174
[Fouss2007] F. Fouss, J.-M. Renders. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation [J], IEEE Trans. Knowledge. Data Eng.2007 19(3):355-369
[Fruchtennan1991]T. M. J. Fruchterman, E. M. Reiengold.. Graph Drawing by Force-directed Placement [J]. Software Practice and Experience.1991,21(11):1129-1164
[Gan2007]G Gan, C. Ma, J. Wu. Data Clustering:Theory, Algorithms, and Applications (ASA-SIAM Series on Statistics and Applied Probability) [M]. Philadelphia, USA, Society for Industrial and Applied Mathematics,2007.
[Ghosh2010] R. Ghosh, K. Lerman. Community Detection Using a Measure of Global Influence [J]. LNCS,2010, 5498:20-35.
[Girvan2002] M. Girvan, M.E.J. Newman. Community structure in social and biological networks [J].Proc. Natl. Acad. Sci.,2002,99 (12):7821-7826.
[Good2010]B.H. Good, Y. de Montjoye, A. Clauset. The performance of modularity maximization in practical contexts [J]. Phys. Rev. E.2010,81(4):046106.
[Gori2007]M. Gori, A. Pucci, Itemrank:A random-walk based scoring algorithm for recommender engines [C]. Proceedings of the 20th International Joint Conference on Artifical Intelligence. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA,2007:2766-2771.
[Granovetter1973] M. Granovetter. The strength of weak ties [J]. Am. J. Sociol.1973,78:1360-1380.
[Guimera2007] R. Guimera, M. Sales-Pardo, L.A.N. Amaral. Module identification in bipartite and directed networks [J]. Phys. Rev. E. 2007,76 (3):036102.
[Gulbahce2008] N. Gulbahce, S Lehmann. The Art of Community Detection[M], Wiley Online Library.2008
[哈贝马斯1993]尤尔根.哈贝马斯.交往行动理论：第1卷[M].重庆：重庆出版社,1993.
[Hare12001] D. Harel, Y. Koren, On clustering using random walks [C], Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science, Springer-Verlag, London, UK,2001: 18-41.
[Hastie2001] T. Hastie. R. Tibshirani, J.H. Friedman [M], The Elements of Statistical Learning, Berlin. Germany: Springer,2001.
[Holmstrom2009] E. Holmstrom, N. Bock,J. Brannlund. Modularity density of network community divisions [J]. Physica D.2009,238(14):1161-1167.
[Homans1950] GC. Homans. The Human Groups [M]. New York,:Harcourt, Brace & Co,1950.
[Kernighan1970] B.W. Kernighan, S. Lin. An efficient heuristic procedure for partitioning graphs [J]. Bell Syst. Tech.J.1970,49:291-307.
[Kim2010]Y. Kim, SW. Son, H. Jeong. Finding Communities in Directed Networks [J]. Phys. Rev. E.2010,81(1): 016103
[Kleinl993] D.J. Klein, M. Randic. Resistance distance [J]. Journal of Mathematical Chemistry.1993,12(l):81-95.
[Kottak 2004] C.P. Kottak. Cultural Anthropology [M]. New York, USA:McGraw-Hill,2004.
[Krause2003] A.E. Krause, K.A. Frank, D.M. Mason, R.E. Ulanowicz, W.W. Taylor. Compartments revealed in food-web structure [J], Nature,2003,426:282-285.
[Krishnamurthy2000] B. Krishnamurthy, J. Wang. On network-aware clustering of web clients [J]. SIGCOMM Comput. Commun. Rev. 2000,30 (4):97-110.
[Kumar2010] R. Kumar. J. Novak. A. Tomkins. Link Mining:Model, Algorithms, and Applications [M]. New York. USA:Springer.2010.
[Lehmann2007] S. Lehmann. L.K. Hansen. Deterministic modularity optimization [J]. Eur. Phys. J. B.2007,60: 83-88.
[Leicht2008] E. A. Leicht. M. E. J. Newman. Community Structure in Directed Networks [J]. Phys. Rev. Lett.2008, 100(11):118703
[Liu2007]X. Liu, D. Li, S. Wang, Z. Tao. Effective algorithm for detecting community structure in complex networks based on GA and clustering [C]. ICCS '07:Proceedings of the 7th International Conference on Computational Science, Part Ⅱ, Springer-Verlag, Berlin, Heidelberg,2007,657-664.
[Lorrain 1971] F. Lorrain, H. White. Structural equivalence of individuals in social networks [J]. J. Math. Sociol.1 (1971)49-80.
[Lusseau 2004JD. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, S. M. Dawson. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-last associations. Can geographic isolation explain this unique trait? [J]. Behavioral Ecology And Sociobiology,2004,54(4):396-405
[Massen2005] C.P. Massen, J.P.K. Doye. Identifying communities within energy landscapes [J], Phys. Rev. E.2005, 71 (4):046101.
[Medus2005] A. Medus. G. Acuna, C.O. Dorso. Detection of community structures in networks via global optimization [J]. Physica A.2005,358:593-604.
[Mei2009]J. Mei, S. He, G. Shi, Z. Wang, W. Li. Revealing network communities through modularity maximization by a contraction-dilation method [J]. New J. Phys.2009,11 (4):043025.
[Moody2003] J. Moody, D.R. White. Structural cohesion and embeddedness:A hierarchical concept of social groups [J]. Am. Sociol. Rev.2003,68 (1):103-127.
[MufT2005]S. Muff, F. Rao, A. Caflisch. Local modularity measure for network clusterizations [J]. Phys. Rev. E. 2005,72 (5):056107.
[Newman2003] M.E.J. Newman. The structure and function of complex networks [J]. SIAM Rev.2003,45 (2): 167-256.
[Newman2004a] M. E. J. Newman, M. Girvan. Finding and evaluating community structure in networks[J]. Physical Review E,2004,69(2):026113.
[Newman2004b] M. E. J. Newman. Analysis of weighted networks [J]. Physical Review E,2004,70(5):056131.
[Newman2004c] M. E. J. Newman. Fast algorithm for detecting community structure in networks[J]. Physical Review E,2004,69(6):066133.
[Newman2004d] M.E.J. Newman, Detecting community structure in networks [J]. The European Physical J. B, 2004,38 (2):321-330.
[Newman2006a] M.E.J. Newman. From the cover:Modularity and community structure in networks [J], Proc. Natl. Acad. Sci. USA.2006,103:8577-8582.
[Newman2006b] M.E.J. Newman. Finding community structure in networks using the eigenvectors of matrices [J]. Phys. Rev. E.2006,74 (3):036104.
[Nicosia2009] V. Nicosia, G. Mangioni, V. Carchiolo, M. Malgeri. Extending the definition of modularity to directed graphs with overlapping communities [J]. J. Stat. Mech.2009, P03024.
[Noack2009] A. Noack, R. Rotta. Multi-level algorithms for modularity clustering [C]. SEA'09:Proceedings of the 8th International Symposium on Experimental Algorithms, Springer-Verlag, Berlin. Heidelberg,2009,257-268.
[Palla2005] G. Palla, I. Derenyi,1. Farkas, T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature,2005,435:814818.
[Palmer2003] C.R. Palmer, C. Faloutsos. Electricity based external similarity of categorical attributes [C], Proceedings of PAKDD 2003,2003:486-500.
[Pimm 1979] S.L. Pimm. The structure of food webs [J]. Theoret. Popul. Biol.1979,16:144-158.
[Quinn1979] N. Quinn, M. Breur. A force directed component placement procedure for printed circuit boards [J]. IEEE Trans, on Circuits and Systems.1979, CAS-26 (6):377-388.
[Reddy2002] K.P. Reddy, M. Kitsuregawa, P. Sreekanth, S.S. Rao. A graph based approach to extract a neighborhood customer community for collaborative filtering [C]. Proceedings of the Second International Workshop on Databases in Networked Information Systems, Springer-Verlag, London, UK,2002,188-200.
[Reichardt2006] J. Reichardt, S. Bornholdt. Statistical mechanics of community detection[J]. Physical Review E. 2006,74(1):016110-1-14
[Rives2003] A.W. Rives, T. Galitski. Modular organization of cellular networks [J]. Proc. Natl. Acad. Sci. USA. 2003,100(3):1128-1133.
[Roiger2003] R.J. Roiger, M. W. Geatz. Data Mining:A Tutorial-based Primer [M]. Addison-Wesley.2003
[Ruan2007]J. Ruan, W. Zhang. An efficient spectral algorithm for network community discovery and its applications to biological and social networks [C].1CDM'07:Proceedings of the 2007 Seventh IEEE International Conference on Data Mining. IEEE Computer Society, Washington, DC. USA.2007,643-648.
[Sade1972]D. S. Sade. Sociometrics of Macaca mulatta:I. Linkages and cliques in grooming matrices [J]. Folia Primatologica.1972.18:196-223.
|Saerens2004] M. Saerens, F. Fouss, L. Yen, P. Dupont. The principal component analysis of a graph and its relationships to spectral clustering [C], Proc. Eur. Conf. on Machine Learning,2004. URL citeseer.ist.psu.edu/saerens04principal.html.
[Schaeffer2007] S.E. Schaeffer. Graph clustering [J]. Comput. Sci. Rev.2007,1 (1):27-64.
[Scott20001]J. Scott. Social Network Analysis:A Handbook [M]. London, UK:SAGE Publications,2000.
[Shen2009]H. Shen, X. Cheng, K. Cai, M.-B. Hu. Detect overlapping and hierarchical community structure in
[沈华伟2008]沈华伟,程学旗,陈海强,刘悦.基于信息瓶颈的社区发现[J].计算机学报,2008,31(4):677-685.networks [J]. Physica A.2009,388:1706-1712.
[Simon1962] H. Simon. The architecture of complexity [J]. Proc. Am. Phil. Soc.1962,106 (6):467-482.
[Spirin2003] V. Spirin, L.A. Mirny. Protein complexes and functional modules in molecular networks [J]. Proc. Natl. Acad. Sci. USA,2003,100 (21):12123-12128.
[Steenstrup2001] M. Steenstrup. Cluster-Based Networks [M]. USA:Addison Wesley,2001
[Suaris 1988] P.R. Suaris, G. Kedem., An algorithm for quadrisection and its application to standard cellplacement [J]. IEEE Trans. Circuits Syst..1988,35:294-303.
[Sun2009]Y. Sun,B.Danila,K.Josic,K.E.Basslen Improved community structure detection using a modified fine-tuning s[rategy[J].Europhys.Lett.2009,86(2):28004.
[苏淳2007]苏淳.概率论[M].北京：科学出版社,2007.
[Tong2008]H.Tong,c.Faloutsos,J.-Y. Pan.Random walk with restart:Fast Solutions and applications[J].Knowl. Inf Syst.2008,14(3):327-346.
[Tasgin2007]M.Tasgin,A.Herdagdelen,H.Bingol.Community detection in complex networks using genetic algorithms[J].eprint arXiv:0711.0491.
[Tyler2005]J. R.Tyler, D.M.Wilkinson,B.A.Huberman.E-Mail as Spectroscopy:Automated Discovery of Community Structure within Organizations[J].The Information Society.20¨05,22(2):143-153
[王林2010]王林,藏冠中,赵换成, 一种新的评价社区结构的模块度研究[J].计算机工程,2010,36(14):227-232.
[Wassennan1994] S.Wasserman,K.Faust.Social Network Analysis[M].Cambridge,UK:Cambridge University Press.1994.
[Weiss1955]R.S.Weiss.E.Jacobson.A method for the analysis of the structure of complex organizations[J].Am. Sociol.Rev.1955.20:661-668.
[White2003]S.White,P.Smyth.Algorthms for estimating relative importance in networks[C].Proceedings of thee Ninth ACM SIGKDD International Conference on Knowledge Diseovery alld Data Mining.ACM,New York.NY, USA.2003:266-275.
[White2005]S.White,P. Smyth. A spectral clustering approach to finding communities in graphs[C].Proceedsngs of SIAM Intemational Conference on Data Mining.2005.76-84.
[Xiang2009]B.Xiang.E.-H.Chen,T. Zhou. Finding community structure based on subgraph sinlilarity[J]. Complex Networks,Springer Verlag,Berlin/Heidelberg,Germany,2009,207:73-81.
[Yan2012]B.Yan,S.Gregory.Derecting community structure in networks using edge prediction methods[J]Arxiv. 2012.arXiv:1201.3466
[Yen2007]L.Yen,F.Fouss,C.Decaestecker, P. Francq, M.Saerens.Graph nodes clustering based 011 the commute-time kernel[J] Lecture Nores in Computer Science.2007,4426:1037-1045.
[Yen2009]L.Yen.F.Fouss,C.Decaestecker P Francq,M.Saerens,Graph nodes clustering witll the sigmoid commute-time kernel:A comparative study [J].Data Knowl.Eng.2009.68(3):338-361.
[zachary1997]W.W. Zachary. An Information Flow Model for Conflict and Fission in Small Groups[J]. Joumal of Anthropological.1977,33(4):452-473
[Zhang2008] Y. Zhang, A.J. Friend, A.L. Traud, M.A. Porter, J.H. Fowler, P.J. Mucha. Community structure in congressional cosponsorship networks [J]. Physica A.2008,387(7):1705-1712.
[Zhou2003]H. Zhou. Network landscape from a brownian particle's perspective [J]. Phys. Rev. E. 2003,67 (4): 041908.
[Zhou2004]H. Zhou, R. Lipowsky. Network brownian motion:A new method to measure vertex-vertex proximity and to identify communities and subcommunities [J]. Lect. Notes Comput. Sci. 2004,3038:10621069.