复杂网络中的社团检测问题研究
|
摘要
近年来,由于信息技术的飞速发展,科学家和学者们能够越来越容易地在现实世界中收集到高通量的网络数据,这使得复杂网络的研究变得炙手可热起来。除了Watts和Strogatz在1998年发现的小世界特性以及Barabasi和Albert在1999年发现的无标度(尺度)特性外,网络的社团(社区、模块)结构特性被认为是复杂网络中最重要的统计特性之一。目前,关于网络中的社团仍然不存在统一的定义,通常指的是满足下面条件的节点子集：子集内部节点之间具有稠密的连接,而与子集外部的节点具有稀疏的连接。研究表明,网络的这种社团结构与某些功能属性有着紧密的联系,比如网络的鲁棒性和信息快速传递特性等。因此在网络中描述和检测这些社团结构具有重要的实际意义并已成为近几年来的研究热点。
本论文中,我们主要关注复杂网络中社团结构检测相关问题的研究,取得的主要研究成果如下：
1.提出了一种新的社团检测方法-JEOMD。该方法以加入惩罚项的模块密度函数D作为指标函数,并使用跳跃极值最优化方法来优化该指标函数,能够得到网络的层次分割结果。在一组真实网络上的实验表明,与基于模块化函数Q的优化方法相比,JEOMD方法能够更有效地检测出网络中存在的不同层次和不同规模的社团结构。在该组真实网络及其对应的随机网络上的对比实验表明,加入惩罚项的模块密度函数D作为社团检测的指标函数在一定程度上比模块化函数Q更有效。
2.提出了一个新的衡量社团划分质量的指标函数,称之为标准化模块密度(normalized modularity density-NMD)。在示例网络中证明了NMD能够改善模块化函数Q中存在的分辨率极限问题；证明了NMD与图分割中广泛应用的normalized-cut目标函数存在着紧密的联系,即当社团数目m已知时,最大化标准化模块密度相当于最小化目标函数normalized-cut。使用改进的模拟退火算法优化指标NMD。在一组模拟网络上的实验表明,与基于模块化函数Q的优化方法相比,基于NMD的方法能够取得更高的检测正确率；在一组真实网络上的实验表明,基于NMD的方法能够检测出网络中更精细的模块结构,从而为NMD能够改善Q的分辨率问题提供了更进一步的证据；
把指标函数NMD和D推广到其加权形式NMDω和Dw,并用于在加权网络中进行社团检测。分析了加权模块化函数Qw同样存在分辨率极限问题；指出了加权模块密度函数Dw存在的负社团问题；在两个实例网络上证明了NMDω不仅能够克服Qw中存在的分辨率极限问题,而且能够避免Dw中出现的负社团问题。为了比较指标NMDω与Qw和Dw在加权网络社团检测中的性能,使用模拟退火算法实现三个指标的优化。在一组模拟网络上的实验表明,优化NMDω指标能够取得比优化Qw和Dw更高的检测正确率；在一组真实网络上的实验表明,优化NMDω指标,不仅能够从加权网络中检测出精细尺度下的社团,尤其是优化Qw所不能检测出来的小而稠密的社团,而且能够避免优化Dw时出现的负社团问题。
3.提出了一种基于自适应核仿射传播的网络社团检测方法-AKAP。在该方法中,标准化的马尔可夫扩散核(Markov diffusion kernel)被用来隐式地衡量节点之间的非相似度,引入自适应仿射传播方法优化得到的非相似度矩阵。在模拟网络上的实验表明,与Newman快速算法相比,AKAP方法能够取得更高的检测正确率；在一组真实网络上的实验表明,AKAP方法能够有效地检测出网络中存在的有意义的社团结构和包含的社团数目。
4.提出了一种有效的网络节点的可视化方法。在该方法中,定义了一种新的节点间距离,将得到的距离矩阵作为全局保形映射Isomap的测地线距离,应用Isomap方法得到网络的二维可视化结果。在模拟网络上的实验表明,与基于能量模型的可视化方法相比,我们的方法能够更好地保持原始网络中节点的局部和全局相似性,且当网络具有清晰的社团结构时,得到的二维可视化点集也具有紧凑的聚类特性,因此能够从可视化结果中判断原始网络是否具有社团结构特性,也可以对可视化的结果继续采用传统的聚类方法进行聚类以得到网络每个社团的具体成员。
In recent years, along with the high-speed development of information technique, complex network has become a growing research field partly as a result of the increas-ing availability of a huge number of networks in the real world. Besides small world effect found by Watts and Strogatz in 1998 and scale-free effect found by Barabasi and Albert in 1999, community(module) structure has been considered to be one of the most important characteristics in complex networks. Until now, there isn't a pre-cise definition of community. Generally speaking, community refers to such subgraph within which vertex-vertex connections are dense, but outside which connections are relatively sparse. The investigations show that this kind of community structure has close relationship with some functionality such as robustness and fast diffusion, etc. So characterizing and detecting such community structure has very important practical significance and has become a research hot spot.
The related problems on community detection in complex networks are studied in this paper, and the main results are as follows:
1. A novel community detection algorithm is presented which is called JEOMD. It uses improved modularity density D with penalty term as the objective function and optimizes this objective through jumping extremal optimization technique. As a result, hierarchical partition of the given network can be obtained. Exper-imental results on several real-world networks show that, compared with those methods based on optimizing modularity Q, JEOMD can detect out hidden com-munity structure with different hierarchies and different scales more efficiently; comparative experiments on those real-world networks and their random counter-parts show that D with penalty term is more efficient than modularity function Q in some aspects.
2. A novel local quantitative measure called normalized modularity density N M D is proposed. The advantage that NMD can improve the resolution limit of Q is proved. The close connection between NMD and normalized-cut is derived; that is to say if the number of communities m is predetermined, maximizing the measure NMD equals to minimizing normalized-cut. Simulated annealing algorithm is designed to optimize the indexes NMD. Experiments on a suit of computer-generated networks show that, compared with Q-based optimization methods, optimizing NMD can obtained the higher accuracy; comparative ex-periment on several real-world networks show that optimizing NMD can detect out finer community structure, which provides further evidence that NMD can improve the resolution limit of Q;
NMD and D are generalized to their weighted versions. The similar resolu-tion limit problem of Qw and the new emerging negative community problem of Dw is analyzed, and then the related certifications on the advantages of N M Dw to Qw and Dw in these two aspects are derived. In order to compare the perfor-mances of the three indexes, simulated annealing algorithm is used to optimize them. Experiments on a suit of weighted computer-generated networks show that, compared with Qw-based methods, optimizing the index NMDw can ob-tained the higher accuracy; experiments on several real-world networks show that optimizing the index NMDw not only can detect out the community structure with different scales, especially some small and dense communities that optimiz-ing Qw can not detect, but also can avoid the negative community problem in Dw.
3. A method called adaptive kernel affinity propagation (AKAP) is proposed to de-tect communities in networks, in which the normalized Markov diffusion kernel is used to implicitly measure the dissimilarities between different nodes and then adaptive affinity propagation is applied to optimize the obtained dissimilarity matrix. Comparative experiments on computer-generated networks show that AKAP can obtained the higher accuracy than Newman fast algorithm; experi- ments on several real-world networks demonstrate that adaptive kernel affinity propagation can detect the optimal number of communities and the meaningful communities.
4. An efficient visualization method to nodes in complex networks is proposed. A new distance between nodes is defined. The obtained distance matrix is used as the geodesic distance of Isomap and as a result all nodes are projected into a two dimensional plane. The experiments on computer-generated networks show that, compared with energy-based models, the proposed method can keep local and global similarity better in original networks. When the given networks have clear community structure, the projected nodes also have compact clustering property. So whether the original network has community structure or not can be judged by the visualization results, and the detailed community memberships can be obtained by clustering the projected coordinates.
本论文中,我们主要关注复杂网络中社团结构检测相关问题的研究,取得的主要研究成果如下：
1.提出了一种新的社团检测方法-JEOMD。该方法以加入惩罚项的模块密度函数D作为指标函数,并使用跳跃极值最优化方法来优化该指标函数,能够得到网络的层次分割结果。在一组真实网络上的实验表明,与基于模块化函数Q的优化方法相比,JEOMD方法能够更有效地检测出网络中存在的不同层次和不同规模的社团结构。在该组真实网络及其对应的随机网络上的对比实验表明,加入惩罚项的模块密度函数D作为社团检测的指标函数在一定程度上比模块化函数Q更有效。
2.提出了一个新的衡量社团划分质量的指标函数,称之为标准化模块密度(normalized modularity density-NMD)。在示例网络中证明了NMD能够改善模块化函数Q中存在的分辨率极限问题；证明了NMD与图分割中广泛应用的normalized-cut目标函数存在着紧密的联系,即当社团数目m已知时,最大化标准化模块密度相当于最小化目标函数normalized-cut。使用改进的模拟退火算法优化指标NMD。在一组模拟网络上的实验表明,与基于模块化函数Q的优化方法相比,基于NMD的方法能够取得更高的检测正确率；在一组真实网络上的实验表明,基于NMD的方法能够检测出网络中更精细的模块结构,从而为NMD能够改善Q的分辨率问题提供了更进一步的证据；
把指标函数NMD和D推广到其加权形式NMDω和Dw,并用于在加权网络中进行社团检测。分析了加权模块化函数Qw同样存在分辨率极限问题；指出了加权模块密度函数Dw存在的负社团问题；在两个实例网络上证明了NMDω不仅能够克服Qw中存在的分辨率极限问题,而且能够避免Dw中出现的负社团问题。为了比较指标NMDω与Qw和Dw在加权网络社团检测中的性能,使用模拟退火算法实现三个指标的优化。在一组模拟网络上的实验表明,优化NMDω指标能够取得比优化Qw和Dw更高的检测正确率；在一组真实网络上的实验表明,优化NMDω指标,不仅能够从加权网络中检测出精细尺度下的社团,尤其是优化Qw所不能检测出来的小而稠密的社团,而且能够避免优化Dw时出现的负社团问题。
3.提出了一种基于自适应核仿射传播的网络社团检测方法-AKAP。在该方法中,标准化的马尔可夫扩散核(Markov diffusion kernel)被用来隐式地衡量节点之间的非相似度,引入自适应仿射传播方法优化得到的非相似度矩阵。在模拟网络上的实验表明,与Newman快速算法相比,AKAP方法能够取得更高的检测正确率；在一组真实网络上的实验表明,AKAP方法能够有效地检测出网络中存在的有意义的社团结构和包含的社团数目。
4.提出了一种有效的网络节点的可视化方法。在该方法中,定义了一种新的节点间距离,将得到的距离矩阵作为全局保形映射Isomap的测地线距离,应用Isomap方法得到网络的二维可视化结果。在模拟网络上的实验表明,与基于能量模型的可视化方法相比,我们的方法能够更好地保持原始网络中节点的局部和全局相似性,且当网络具有清晰的社团结构时,得到的二维可视化点集也具有紧凑的聚类特性,因此能够从可视化结果中判断原始网络是否具有社团结构特性,也可以对可视化的结果继续采用传统的聚类方法进行聚类以得到网络每个社团的具体成员。
In recent years, along with the high-speed development of information technique, complex network has become a growing research field partly as a result of the increas-ing availability of a huge number of networks in the real world. Besides small world effect found by Watts and Strogatz in 1998 and scale-free effect found by Barabasi and Albert in 1999, community(module) structure has been considered to be one of the most important characteristics in complex networks. Until now, there isn't a pre-cise definition of community. Generally speaking, community refers to such subgraph within which vertex-vertex connections are dense, but outside which connections are relatively sparse. The investigations show that this kind of community structure has close relationship with some functionality such as robustness and fast diffusion, etc. So characterizing and detecting such community structure has very important practical significance and has become a research hot spot.
The related problems on community detection in complex networks are studied in this paper, and the main results are as follows:
1. A novel community detection algorithm is presented which is called JEOMD. It uses improved modularity density D with penalty term as the objective function and optimizes this objective through jumping extremal optimization technique. As a result, hierarchical partition of the given network can be obtained. Exper-imental results on several real-world networks show that, compared with those methods based on optimizing modularity Q, JEOMD can detect out hidden com-munity structure with different hierarchies and different scales more efficiently; comparative experiments on those real-world networks and their random counter-parts show that D with penalty term is more efficient than modularity function Q in some aspects.
2. A novel local quantitative measure called normalized modularity density N M D is proposed. The advantage that NMD can improve the resolution limit of Q is proved. The close connection between NMD and normalized-cut is derived; that is to say if the number of communities m is predetermined, maximizing the measure NMD equals to minimizing normalized-cut. Simulated annealing algorithm is designed to optimize the indexes NMD. Experiments on a suit of computer-generated networks show that, compared with Q-based optimization methods, optimizing NMD can obtained the higher accuracy; comparative ex-periment on several real-world networks show that optimizing NMD can detect out finer community structure, which provides further evidence that NMD can improve the resolution limit of Q;
NMD and D are generalized to their weighted versions. The similar resolu-tion limit problem of Qw and the new emerging negative community problem of Dw is analyzed, and then the related certifications on the advantages of N M Dw to Qw and Dw in these two aspects are derived. In order to compare the perfor-mances of the three indexes, simulated annealing algorithm is used to optimize them. Experiments on a suit of weighted computer-generated networks show that, compared with Qw-based methods, optimizing the index NMDw can ob-tained the higher accuracy; experiments on several real-world networks show that optimizing the index NMDw not only can detect out the community structure with different scales, especially some small and dense communities that optimiz-ing Qw can not detect, but also can avoid the negative community problem in Dw.
3. A method called adaptive kernel affinity propagation (AKAP) is proposed to de-tect communities in networks, in which the normalized Markov diffusion kernel is used to implicitly measure the dissimilarities between different nodes and then adaptive affinity propagation is applied to optimize the obtained dissimilarity matrix. Comparative experiments on computer-generated networks show that AKAP can obtained the higher accuracy than Newman fast algorithm; experi- ments on several real-world networks demonstrate that adaptive kernel affinity propagation can detect the optimal number of communities and the meaningful communities.
4. An efficient visualization method to nodes in complex networks is proposed. A new distance between nodes is defined. The obtained distance matrix is used as the geodesic distance of Isomap and as a result all nodes are projected into a two dimensional plane. The experiments on computer-generated networks show that, compared with energy-based models, the proposed method can keep local and global similarity better in original networks. When the given networks have clear community structure, the projected nodes also have compact clustering property. So whether the original network has community structure or not can be judged by the visualization results, and the detailed community memberships can be obtained by clustering the projected coordinates.
引文
[1]D. Watts, S. Strogatz. Collective dynamics of'small-world'networks. Nature, 393(6):440-442,1998.
[2]A. L. Barabasi, R. Albert. Emergence of scaling in random networks. Science, 286(5439):509-512,1999.
[3]G. Alexanderson. Euler and koigsberg's bridges:a historical view. Bulletin of the American Mathematical Society,43(4):567-573,2006.
[4]P. Erdos, A. Renyi. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences,5:17-61,1960.
[5]S. H. Strogatz. Exploring complex networks. Nature,410:268-276,2001.
[6]D. Simard, L. Nadeau, H. Kroge. Fastest learning in small world neural networks. Physics Letters A,336(1):8-15,2005.
[7]J. J. Torres, et al. Influence of topology on the performance of a neural network. Neurocomputing,58-60:229-234,2004.
[8]S. Yang, S. Luo, J. Li. Building multi-layer small world neural network. Inter-national Symposium on Neural Networks (ISNN),3971:695-700,2006.
[9]S. Yang, S. Luo, J. Li. An extended model on self-organizing map. International Conference on Neural Information Processing (ICONIP),4232:987-994,2006.
[10]D. Stauffer, A. Aharony, L. F. Costa, et al. Efficient hopfield pattern recognition on a scale-free neural network. The European Physical Journal B,32:395-399, 2003.
[11]L. G. Morelli, G. Abramson, M. N. Kuperman. Associative memory on a small-world neural network. The European Physical Journal B,38(3):495-500,2004.
[12]S. Zhang, G. Jin, X. S. Zhang, et al. Discovering functions and revealing mecha-nisms at molecular level from biological networks. Proteomics,7(16):2856-2869, 2007.
[13]G. Jin, S. Zhang, X. S. Zhang, et al. Hubs with network motifs organize mod-ularity dynamically in the protein-protein interaction network of yeast. PLoS ONE,2(11):e1207,2007.
[14]R. Guimera, L. A. N. Amaral. Cartography of complex networks:modules and universal a roles. Journal of Statistical Mechanics:Theory and Experiment, page P02001,2005.
[15]R. Guimera, L. A. N. Amaral. Functional cartography of complex metabolic networks. Nature,433:895-900,2005.
[16]L. A. N. Amaral, A. Scala, M. Barthelemy, et al. Classes of small-world net-works. Proceedings of the National Academy of Science of the USA(PNAS), 97(21):11149-11152,2000.
[17]M. E. J. Newman. The structure of scientific collaboration networks. Proceedings of the National Academy of Science of the USA(PNAS),97:404-409,2001.
[18]S. Redner. How popular is your paper? an empirical study of the citation distribution. The European Journal B,4:131-134,1998.
[19]H. Jeong, S. Mason, A. L. Barabasi, et al. Lethality and centrality in protein networks. Nature,411:41-42,2001.
[20]H. Jeong, B. Tombor, R. Albert, et al. The large-scale organization of metabolic networks. Nature,407:651-654,2000.
[21]C. F. M. Faloutsos, P. Faloutsos. On power-law relationships of the internet topology. Comput. Commun. Rev.,29:251-260,1999.
[22]A. V. A. Vazquez, R. Pastor-Satorras. Large-scale topological and dynamical properties of the internet. Physical Review E,65:066130,2002.
[23]R. Albert, H. Jeong, A. L. Barabasi. Diameter of the world wide web. Nature, 401:130-131,1999.
[24]D. H. Zanette. Dynamics of rumor propagation on small-world networks. Physical Review E,65:041908,2002.
[25]A. F. P. Y. Moreno, M. Nekovee. Dynamics of rumor spreading in complex net-works. Physical Review E,69:066130,2004.
[26]L. A. Meyers, B. Pourbohloul, M. E. J. Newman, et al. Network theory and sars: predicting outbreak diversity. Journal of Theoretical Biology,232:71-81,2005.
[27]M. J. Keeling, K. T. D. Eames. Networks and epidemic models. Journal of the royal society interface,2(4):295-307,2005.
[28]V. Colizza, M. B. A. Barrat, et al. The role of the airline transportation network in the prediction and predictability of global epidemics. Journal of the royal society interface,103(7):2010-2015,2006.
[29]R. Pastor-Satorras, A. Vespignani. Immunization of complex networks. Physical Review E,65:036104,2002.
[30]Z. Dezso, A. L. Barabasi. Halting viruses in scale-free networks. Physical Review E,65:055103,2002.
[31]R. Cohen, D.Ben-Avraham, S. Havlin. Efficient immunization strategies for com-puter networks and populations. Physical Review Letters,91:247901,2003.
[32]W. Q. Duan, Z. Chen, e. a. Z. R. Liu. Efficient target strategies for contagion in scale-free networks. Physical Review E,72:026133,2005.
[33]J. Gomez-Gardenes, P. Echenique, Y. Moreno. Immunization of real complex communication networks. The European Physical Journal B,49:259-264,2006.
[34]A. L. Barabasi, E. Bonabeau. Scale-free networks. Scientific American,288:60-69,2003.
[35]L. A. N. Amaral, J. M. Ottino. Augmenting the framework for the study of complex systems. The European physical journal B,38:147-162,2004.
[36]J. Balthrop, S. Forrest, M. E. J. Newman, et al. Technological networks and the spread of computer viruses. Science,304:527-529,2004.
[37]R. Albert, I. Albert, G. L. Nakarado. Structural vulnerability of the north amer-ican power grid. Physical Review E,69:025103,2004.
[38]R. K. R, P. Crucitti, R. Albert, et al. Modeling cascading failures in the north american power grid. The European Physical Journal B,46:101-107,2005.
[39]R. Guimera, L. A. N. Amaral. Modeling the world-wide airport network. The European Physical Journal B,38:381-385,2004.
[40]R. Guimera, S. Mossa, A. Turtschi, et al. The worldwide air transportation net-work:Anomalous centrality, community structure, and cities'global roles. Pro-ceedings of the National Academy of Science of the USA(PNAS),102(22):7794-7799,2005.
[41]M. E. J. Newman, S. Forrest, J. Balthrop. Email networks and the spread of computer viruses. Physical Review E,66:035101,2002.
[42]J. Wang, P. D. Wilde. Properties of evolving e-mail networks. Physical Review E,70:066121,2004.
[43]史定华.网络——探索复杂性的新途径.系统工程学报,20(2)：115-119,2005.
[44]车宏安,顾基发.无标度网络及其系统科学意义.系统工程理论与实践,44(4)：11-16,2004.
[45]姜璐,刘琼慧.系统科学与复杂网络研究.系统辩证学报,13(4)：14-17,2005.
[46]方锦清,汪小帆,刘曾荣.略论复杂性问题和非线性复杂网络系统的研究.科技导报,22(2)：9-12,2004.
[47]M. E. J. Newman. Models of the small world:a review. Journal of Statistical Physics,101:819-841,2000.
[48]M. E. J. Newman, D. J. Watts. Renormalization group analysis of the small-world network model. Physics Letters A,263:341-346,1999.
[49]M. E. J. Newman, D. J. Watts. Scaling and percolation in the small-world net-work model. Physical Review E,60:7332-7342,1999.
[50]R. K. R. Multiple scales in small-world graphs. cond-mat/9904055,1999.
[51]S. N. Dorogovtsev, J. F. F. Mendes. Exactly solvable small-world network. Eu-rophys. Letters,50:1-7,2000.
[52]J. Kleinberg. Navigation in a small world. Nature,406:845-845,2000.
[53]杨波,陈忠,段文奇.基于个体选择的小世界网络结构演化.系统工程,22(12)：1-5,2004.
[54]J. Ozik, B. R. Hunt, E. Ott. Growing networks with geographical attachment preference:Emergence of small worlds. Physical Review E,69:026108,2004.
[55]P. Holme, B. J. Kim. Growing scale-free networks with tunable clustering. Phys-ical Review E,65:026107,2002.
[56]B. Wang, H. Tang, Z. Zhang, et al. Evolving scale-free network model with tunable clustering. International Journal of Modern Physics B,19(26):3951-3959,2005.
[57]G. Bianconi, A. L. Barabasi. Competition and multiscaling in evolving networks. Europhys. Lett.,54:436-442,2001.
[58]F. Chung, L. Y. Lu, T. G. Dewey, et al. Duplication models for biological net-works. Journal of Computational Biology,10(5):677-688,2003.
[59]L. P. Krapivsky, S. Redner. Organization of growing random networks. Physical Review E,63:066123,2001.
[60]A. Vazquez. Disordered networks generated by recursive searches. Europhys. Lett.,54:430-435,2001.
[61]A. Vazquez. Growing network with local rules:Preferential attachment, cluster-ing hierarchy and degree correlations. Physical Review E,67:056104,2003.
[62]J. Saramaki, K. Kaski. Scale-free networks generated by random walkers. Physica A,341:80-86,2004.
[63]章忠志.复杂网络的演化模型研究[博士论文].大连理工大学管理科学与工程,2006.
[64]G. Palla, I. Derenyi, I. Farkas, et al. Uncovering the overlapping community structure of complex networks in nature and society. Nature,435:814-818,2005.
[65]F. Radicchi, C. Castellano, F. Cecconi, et al. Defining and identifying com-munities in networks. Proceedings of the National Academy of Science of the USA(PNAS),101 (9):2658-2663,2004.
[66]M. E. J. Newman, M. Girvan. Finding and evaluating community structure in networks. Physical Review E,69(2):026113,2004.
[67]B. W. Kernighan, S. Lin. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal,49:291-307,1970.
[68]M. E. J. Newman. A measure of betweenness centrality based on random walks. Social Networks,27(1):39-54,2005.
[69]H. Balakrishnan, N. Deo. Discovering communities in complex networks. In the Proceedings of the 44th ACM Southeast Conference, pages 280-285,2006.
[70]R. S. Burt. Positions in networks. Social Forces,55:93-122,1976.
[71]M. Girvan, M. E. J.. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Science of the USA(PNAS), 99:7821-7826,2002.
[72]M. E. J. Newman. Fast algorithm for detecting community structure in networks. Physical Review E,69:066133,2004.
[73]N. Bock, E. Holmstrom, J. Brannlund. Optimized network clustering by jumping sub-optimal dendrograms. http://arxiv.org/abs/0711.1603,2007.
[74]M. E. J. Newman. Finding community structure in networks using the eigenvec-tors of matrices. Bioinformatics,74:036104,2006.
[75]L. Donetti, M.. A. Munoz. Improved spectral algorithm for the detection of network communities. AIP Conference Proceedings,779:104-107,2005.
[76]S. White, P. Smyth. A spectral clustering approach to finding communities in graphs. SIAM International Conference on Data Mining,2005.
[77]L. Angelini, S. Boccaletti, D. Marinazzo, et al. Identification of network modules by optimization of ratio association. Chaos,17(2):023114,2007.
[78]G. W. Flake, S. Lawrence, C. L. Giles. Efficient identification of web communities. Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 150-160,2000.
[79]F. Wu, B. A. Huberman. Finding communities in linear time:a physics approach. The European Physics Journal B,38:331-338,2004.
[80]S. Boccaletti, M. Ivanchenko, V. Latora, et al. Detection of complex networks modularity by dynamical clustering. Physical Review E,75:045102,2007.
[81]A. Clauset, M. E. J. Newman, C. Moore. Finding community structure in very large networks. Physical Review E,70:066111,2004.
[82]J. Duch, A. Arenas. Community detection in complex networks using extremal optimization. Physical Review E,72:027104,2005.
[83]M. Young, J. Saner, G. Csdrdi. An agent-based algorithm for detecting commu-nity structure in networks. cond-mat/0408263.
[84]S. Fortunato, M. Barthelemy. Resolution limit in community detection. Pro-ceedings of the National Academy of Science of the USA(PNAS),104(1):36-41, 2007.
[85]J. P. Bagrow, E. M. Bollt. Local method for detecting communities. Physical Review E,72:046108,2005.
[86]A. Clauset. Finding local community structure in networks. Physical Review E, 72:026132,2005.
[87]J. P..Bagrow. Evaluating local community methods in networks. Journal of Statistical Mechanics:Theory and Experiment, P05001,2008.
[88]D. B. Vincent, et al. Fast unfolding of communities in large networks. Journal of Statistical Mechanics:Theory and Experiment, page P10008,2008.
[89]S. Muff, F. Rao, A. Caflisch. Local modularity measure for network clusteriza-tions. Physical Review E,72:056107,2005.
[90]Z. Li, S. Zhang, R. S. Wang, et al. Quantitative function for community detection. Physical Review E,77:036109,2008.
[91]J. M. Kumpula, J. Saramaki, K. Kaski, et al. Limited resolution and multiresolu-tion methods in complex network community detection. Fluctuation and Noise Letters,7:209-214,2007.
[92]D. Hristo. A scalable multilevel algorithm for graph clustering and community structure detection. WAW, pages 117-128,2006.
[93]A. Arenas, A. Fernandez, S. Gomez. Multiple resolution of the modular structure of complex networks. New Journal of Physics,10:05039,2008.
[94]G. Yan, T. Zhou, B. Hu, et al. Efficient routing on complex network. Physical Review E,73:046108,2006.
[95]N. A. Alves. Unveiling community structures in weighted networks. Physical Review E,76:036101,2007.
[96]I. Farkas, G. Palla, T. Vicsek. Weighted network modules. New Journal of Physics,9(6):180-198,2007.
[97]S. H. Zhang, R. S. Wang, X. S. Zhang. Identification of overlapping commu-nity structure in complex networks using fuzzy c-means clustering. Physica A, 374:483-490,2007.
[98]S. H. Zhang, R. S. Wang, X. S. Zhang. Uncovering fuzzy community structure in complex networks. Physical Review E,76:046103,2007.
[99]M. Rosvall, C. T. Bergstrom. An information-theoretic framework for resolving community structure in complex networks. Proceedings of the National Academy of Science of the USA(PNAS),104(18):7327-7331,2007.
[100]S. Boettcher, A. G. Percus. Optimization with extremal dynamics. Physical Review Letter,86:5211-5214,2001.
[101]S. Boettcher, A. G. Percus. Extremal optimization for graph partitioning. Phys-ical Review E,64:026114,2001.
[102]A. J. Enright, C. A. Ouzounis. Biolayout-an automatic graph layout algorithm for similarity visualization. Bioinformatics,17(9):853-854,2001.
[103]W. W. Zachary. An information flow model for conflict and fission in small groups. Journal of Anthropological Research,33:452-473,1977.
[104]M. E. J. Newman. The structure and function of complex networks. Society for Industrial and Applied Mathematics (SIAM) Review,45:167-256,2003.
[105]R. Guimera, L. Danon, A. Diaz-Guilera, et al. Self-similar community structure in a network of human interactions. Physical Review E,68:065103,2003.
[106]T. Roxborough, A. Sen. Graph clustering using multiway ratio cut. Proceedings of Graph Drawing Symposium,1353:291-296,1997.
[107]J. Shi, J. Malik. Normalized cuts and image segmentation. IEEE Trans on Pattern Analysis and Machine Intelligence,22(8):888-905,2000.
[108]I. Dhillon, Y. Guan, B. Kulis. A unified view of kernel k-means, spectral clustering and graph cuts. Technical Report UTCS-TR-04-25,2004.
[109]L. Danon, A. Diaz-Guilera, J. Duch, et al. Comparing community structure identification. Journal of Statistical Mechanics:Theory and Experiment, page P09008,2005.
[110]S. Fortunato, C. Castellano. Community detection in graphs. http://arxiv.org/abs/0712.2716,2007.
[111]Y. Fan, et al. Accuracy and precision of methods for community identification in weighted networks. Physica A,377:363-372,2007.
[112]T. Heimo, J. M. Kumpula, K. Kaski, et al. Detecting modules in dense weighted networks with the potts method. Journal of Statistical Mechanics:Theory and Experiment, page P08007,2008.
[113]J. M. Kumpula, J. Saramaki, K. Kaski, et al. Limited resolution in complex network community detection with potts model approach. European Physical Journal B,56:41-45,2007.
[114]A. Lancichinetti, S. Fortunato, F. Radicchi. Benchmark graphs for testing com-munity detection algorithms. Physical Review E,78:046110,2008.
[115]J. Shawe-Taylor, N. Cristianini. Kernel methods for pattern analysis. Cambridge University Press,2004.
[116]F. Fouss, L. Yen, A. Pirotte, et al. An experimental investigation of graph kernels on a collaborative recommendation task. Sixth IEEE International Conference on Data Mining (ICDM'06), pages 863-868,2006.
[117]B. J. Frey, D. Dueck. Clustering by passing messages between data points. Sci-ence,315(5814):972-976,2007.
[118]L. Wang, C. Leckie, K. Ramamohanarao, et al. Automatically determining the number of clusters in unlabeled data sets. IEEE Transactions on Knowledge and Data Engineering.,21(3):335-350,2009.
[119]王开军,张军英,李丹,et al.自适应仿射传播聚类.自动化学报,33(12)：1242-1246,2007.
[120]R. I. Kondor, J. Lafferty. Diffusion kernels on graphs and other discrete struc-tures. Proceedings of the 19th International Conference on Machine Learn-ing(ICML), page 315-322,2002.
[121]A. J. Smola, R. I. Kondor. Kernels and regularization on graphs. Proceedings of the Conference on Learning Theory (COLT) and Kernels Workshop, pages 144-158,2003.
[122]F. Fouss, A. Pirotte, J. M. Renders, et al. Random-walk computation of similari-ties between nodes of a graph, with application to collaborative recommendation. IEEE Transactions on Knowledge and Data Engineering,19(3):355-369,2007.
[123]S. Lafon, A. B. Lee. Diffusion maps and coarse-graining:A unified framework for dimensionality reduction. IEEE Transactions on Pattern Analysis and Machine Intelligence,28(9):1393-1403,2006.
[124]B. Nadler, S. Lafon, R. Coifman, et al. Diffusion maps, spectral clustering and eigenfunctions of fokker-planck operators. Advances in Neural Information Pro-cessing Systems,18:955-962,2006.
[125]S. Zhang, X. M. Ning, X. S. Zhang. Graph kernels, hierarchical clustering, and network community structure:experiment and comparative analysis. European Physical Journal B,68:065103,2003.
[126]E. Leicht, P. Holme, M. E. J. Newman. Vertex similarity in networks. Phys. Rev. E,73(2):026120,2006.
[127]http://www.mathworks.com/matlabcentral/fileexchange/authors/24811.
[128]http://www personal.umich.edu/-mejn/.
[129]V. L. R, D. L. W. Graphsplatting:Visualizing graphs as continuous fields. IEEE Transactions on Visualization and Computer Graphics,9(2):206-212,2003.
[130]C. Li, P. K. Maini. An evolving network model with community structure. Jour-nal of Physics A:Mathematical and General,38:9741-9749,2005.
[131]M. E. J. Newman. Detecting community structure in networks. European Phys-ical Journal B,38(2):321-330,2004.
[132]J. Karhunen, J. Joutsensalo. Generalizations of principal component analysis, optimization problems, and neural networks. Neural Networks,8(4):549-562, 1995.
[133]V. C. Klema. The singular value decomposition:Its computation and some application. IEEE Transaction on Automatic Control, pages 164-176,1980.
[134]T. F. Cox, M. A. A. Cox. Multidimensional Scaling. Chapman and Hall, New York,2000.
[135]S. T. Roweis, L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science,290(5500):2323-2326,2000.
[136]J. B. Tenenbaum, V. d. Silva, J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science,290(12):2319-2323,2000.
[137]曾宪华.流形学习的谱方法相关问题研究[博士论文].北京交通大学计算机与信息技术学院,2009.
[138]F. J. Brandenburg, M. Himsolt, C. Rohrer. An experimental comparison of force-directed and randomized graph drawing algorithms. Proc. Symposium on Graph Drawing (LNCS),1027:76-87,1996.
[139]U. Brandes, S. Cornelsen. Visual ranking of link structures. Proc.7th Inter-national Workshop on Algorithms and Data Structures (WADS),2125:222-233, 2001.
[140]A. Noack. An energy model for visual graph clustering. In Proc.11th Interna-tional Symposium on Graph Drawing,2912:425-436,2004.
[141]D. Auber, Y. Chiricota, F. Jourdan, et al. Multiscale visualization of small world networks. In Proceedings of the 2003 IEEE Symposium on Information Visual-ization, pages 75-81,2003.
[142]J. C Bezdek, R. J. Hathaway. Vat:A tool for visual assessment of (cluster) tendency. Proc. Int'l Joint Conf. Neural Networks (IJCNN'02), pages 2225-2230,2002.
[143]S. Yang, S. Luo, J. Li. A novel visual clustering algorithm for finding community in complex network. International Conference on Advanced Data Mining and Applications(ADMA),4093:396-403,2006.
[144]M. Molloy, B. Reed. A critical point for random graphs with a given degree sequence. Random Structures and Algorithms,6:161-180,1995.
[145]A. L. N. Fred, A. K. Jain. Robust data clustering. IEEE Computer Society Conference on Computer Vision and Pattern Recognition(CVPR),1:128-133, 2003.
[146]L. I. Kuncheva, S. T. Hadjitodorov. Using diversity in cluster ensembles. IEEE International Conference on Systems, Man and Cybernetics,2:1214-1219,2004.
[2]A. L. Barabasi, R. Albert. Emergence of scaling in random networks. Science, 286(5439):509-512,1999.
[3]G. Alexanderson. Euler and koigsberg's bridges:a historical view. Bulletin of the American Mathematical Society,43(4):567-573,2006.
[4]P. Erdos, A. Renyi. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences,5:17-61,1960.
[5]S. H. Strogatz. Exploring complex networks. Nature,410:268-276,2001.
[6]D. Simard, L. Nadeau, H. Kroge. Fastest learning in small world neural networks. Physics Letters A,336(1):8-15,2005.
[7]J. J. Torres, et al. Influence of topology on the performance of a neural network. Neurocomputing,58-60:229-234,2004.
[8]S. Yang, S. Luo, J. Li. Building multi-layer small world neural network. Inter-national Symposium on Neural Networks (ISNN),3971:695-700,2006.
[9]S. Yang, S. Luo, J. Li. An extended model on self-organizing map. International Conference on Neural Information Processing (ICONIP),4232:987-994,2006.
[10]D. Stauffer, A. Aharony, L. F. Costa, et al. Efficient hopfield pattern recognition on a scale-free neural network. The European Physical Journal B,32:395-399, 2003.
[11]L. G. Morelli, G. Abramson, M. N. Kuperman. Associative memory on a small-world neural network. The European Physical Journal B,38(3):495-500,2004.
[12]S. Zhang, G. Jin, X. S. Zhang, et al. Discovering functions and revealing mecha-nisms at molecular level from biological networks. Proteomics,7(16):2856-2869, 2007.
[13]G. Jin, S. Zhang, X. S. Zhang, et al. Hubs with network motifs organize mod-ularity dynamically in the protein-protein interaction network of yeast. PLoS ONE,2(11):e1207,2007.
[14]R. Guimera, L. A. N. Amaral. Cartography of complex networks:modules and universal a roles. Journal of Statistical Mechanics:Theory and Experiment, page P02001,2005.
[15]R. Guimera, L. A. N. Amaral. Functional cartography of complex metabolic networks. Nature,433:895-900,2005.
[16]L. A. N. Amaral, A. Scala, M. Barthelemy, et al. Classes of small-world net-works. Proceedings of the National Academy of Science of the USA(PNAS), 97(21):11149-11152,2000.
[17]M. E. J. Newman. The structure of scientific collaboration networks. Proceedings of the National Academy of Science of the USA(PNAS),97:404-409,2001.
[18]S. Redner. How popular is your paper? an empirical study of the citation distribution. The European Journal B,4:131-134,1998.
[19]H. Jeong, S. Mason, A. L. Barabasi, et al. Lethality and centrality in protein networks. Nature,411:41-42,2001.
[20]H. Jeong, B. Tombor, R. Albert, et al. The large-scale organization of metabolic networks. Nature,407:651-654,2000.
[21]C. F. M. Faloutsos, P. Faloutsos. On power-law relationships of the internet topology. Comput. Commun. Rev.,29:251-260,1999.
[22]A. V. A. Vazquez, R. Pastor-Satorras. Large-scale topological and dynamical properties of the internet. Physical Review E,65:066130,2002.
[23]R. Albert, H. Jeong, A. L. Barabasi. Diameter of the world wide web. Nature, 401:130-131,1999.
[24]D. H. Zanette. Dynamics of rumor propagation on small-world networks. Physical Review E,65:041908,2002.
[25]A. F. P. Y. Moreno, M. Nekovee. Dynamics of rumor spreading in complex net-works. Physical Review E,69:066130,2004.
[26]L. A. Meyers, B. Pourbohloul, M. E. J. Newman, et al. Network theory and sars: predicting outbreak diversity. Journal of Theoretical Biology,232:71-81,2005.
[27]M. J. Keeling, K. T. D. Eames. Networks and epidemic models. Journal of the royal society interface,2(4):295-307,2005.
[28]V. Colizza, M. B. A. Barrat, et al. The role of the airline transportation network in the prediction and predictability of global epidemics. Journal of the royal society interface,103(7):2010-2015,2006.
[29]R. Pastor-Satorras, A. Vespignani. Immunization of complex networks. Physical Review E,65:036104,2002.
[30]Z. Dezso, A. L. Barabasi. Halting viruses in scale-free networks. Physical Review E,65:055103,2002.
[31]R. Cohen, D.Ben-Avraham, S. Havlin. Efficient immunization strategies for com-puter networks and populations. Physical Review Letters,91:247901,2003.
[32]W. Q. Duan, Z. Chen, e. a. Z. R. Liu. Efficient target strategies for contagion in scale-free networks. Physical Review E,72:026133,2005.
[33]J. Gomez-Gardenes, P. Echenique, Y. Moreno. Immunization of real complex communication networks. The European Physical Journal B,49:259-264,2006.
[34]A. L. Barabasi, E. Bonabeau. Scale-free networks. Scientific American,288:60-69,2003.
[35]L. A. N. Amaral, J. M. Ottino. Augmenting the framework for the study of complex systems. The European physical journal B,38:147-162,2004.
[36]J. Balthrop, S. Forrest, M. E. J. Newman, et al. Technological networks and the spread of computer viruses. Science,304:527-529,2004.
[37]R. Albert, I. Albert, G. L. Nakarado. Structural vulnerability of the north amer-ican power grid. Physical Review E,69:025103,2004.
[38]R. K. R, P. Crucitti, R. Albert, et al. Modeling cascading failures in the north american power grid. The European Physical Journal B,46:101-107,2005.
[39]R. Guimera, L. A. N. Amaral. Modeling the world-wide airport network. The European Physical Journal B,38:381-385,2004.
[40]R. Guimera, S. Mossa, A. Turtschi, et al. The worldwide air transportation net-work:Anomalous centrality, community structure, and cities'global roles. Pro-ceedings of the National Academy of Science of the USA(PNAS),102(22):7794-7799,2005.
[41]M. E. J. Newman, S. Forrest, J. Balthrop. Email networks and the spread of computer viruses. Physical Review E,66:035101,2002.
[42]J. Wang, P. D. Wilde. Properties of evolving e-mail networks. Physical Review E,70:066121,2004.
[43]史定华.网络——探索复杂性的新途径.系统工程学报,20(2)：115-119,2005.
[44]车宏安,顾基发.无标度网络及其系统科学意义.系统工程理论与实践,44(4)：11-16,2004.
[45]姜璐,刘琼慧.系统科学与复杂网络研究.系统辩证学报,13(4)：14-17,2005.
[46]方锦清,汪小帆,刘曾荣.略论复杂性问题和非线性复杂网络系统的研究.科技导报,22(2)：9-12,2004.
[47]M. E. J. Newman. Models of the small world:a review. Journal of Statistical Physics,101:819-841,2000.
[48]M. E. J. Newman, D. J. Watts. Renormalization group analysis of the small-world network model. Physics Letters A,263:341-346,1999.
[49]M. E. J. Newman, D. J. Watts. Scaling and percolation in the small-world net-work model. Physical Review E,60:7332-7342,1999.
[50]R. K. R. Multiple scales in small-world graphs. cond-mat/9904055,1999.
[51]S. N. Dorogovtsev, J. F. F. Mendes. Exactly solvable small-world network. Eu-rophys. Letters,50:1-7,2000.
[52]J. Kleinberg. Navigation in a small world. Nature,406:845-845,2000.
[53]杨波,陈忠,段文奇.基于个体选择的小世界网络结构演化.系统工程,22(12)：1-5,2004.
[54]J. Ozik, B. R. Hunt, E. Ott. Growing networks with geographical attachment preference:Emergence of small worlds. Physical Review E,69:026108,2004.
[55]P. Holme, B. J. Kim. Growing scale-free networks with tunable clustering. Phys-ical Review E,65:026107,2002.
[56]B. Wang, H. Tang, Z. Zhang, et al. Evolving scale-free network model with tunable clustering. International Journal of Modern Physics B,19(26):3951-3959,2005.
[57]G. Bianconi, A. L. Barabasi. Competition and multiscaling in evolving networks. Europhys. Lett.,54:436-442,2001.
[58]F. Chung, L. Y. Lu, T. G. Dewey, et al. Duplication models for biological net-works. Journal of Computational Biology,10(5):677-688,2003.
[59]L. P. Krapivsky, S. Redner. Organization of growing random networks. Physical Review E,63:066123,2001.
[60]A. Vazquez. Disordered networks generated by recursive searches. Europhys. Lett.,54:430-435,2001.
[61]A. Vazquez. Growing network with local rules:Preferential attachment, cluster-ing hierarchy and degree correlations. Physical Review E,67:056104,2003.
[62]J. Saramaki, K. Kaski. Scale-free networks generated by random walkers. Physica A,341:80-86,2004.
[63]章忠志.复杂网络的演化模型研究[博士论文].大连理工大学管理科学与工程,2006.
[64]G. Palla, I. Derenyi, I. Farkas, et al. Uncovering the overlapping community structure of complex networks in nature and society. Nature,435:814-818,2005.
[65]F. Radicchi, C. Castellano, F. Cecconi, et al. Defining and identifying com-munities in networks. Proceedings of the National Academy of Science of the USA(PNAS),101 (9):2658-2663,2004.
[66]M. E. J. Newman, M. Girvan. Finding and evaluating community structure in networks. Physical Review E,69(2):026113,2004.
[67]B. W. Kernighan, S. Lin. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal,49:291-307,1970.
[68]M. E. J. Newman. A measure of betweenness centrality based on random walks. Social Networks,27(1):39-54,2005.
[69]H. Balakrishnan, N. Deo. Discovering communities in complex networks. In the Proceedings of the 44th ACM Southeast Conference, pages 280-285,2006.
[70]R. S. Burt. Positions in networks. Social Forces,55:93-122,1976.
[71]M. Girvan, M. E. J.. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Science of the USA(PNAS), 99:7821-7826,2002.
[72]M. E. J. Newman. Fast algorithm for detecting community structure in networks. Physical Review E,69:066133,2004.
[73]N. Bock, E. Holmstrom, J. Brannlund. Optimized network clustering by jumping sub-optimal dendrograms. http://arxiv.org/abs/0711.1603,2007.
[74]M. E. J. Newman. Finding community structure in networks using the eigenvec-tors of matrices. Bioinformatics,74:036104,2006.
[75]L. Donetti, M.. A. Munoz. Improved spectral algorithm for the detection of network communities. AIP Conference Proceedings,779:104-107,2005.
[76]S. White, P. Smyth. A spectral clustering approach to finding communities in graphs. SIAM International Conference on Data Mining,2005.
[77]L. Angelini, S. Boccaletti, D. Marinazzo, et al. Identification of network modules by optimization of ratio association. Chaos,17(2):023114,2007.
[78]G. W. Flake, S. Lawrence, C. L. Giles. Efficient identification of web communities. Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 150-160,2000.
[79]F. Wu, B. A. Huberman. Finding communities in linear time:a physics approach. The European Physics Journal B,38:331-338,2004.
[80]S. Boccaletti, M. Ivanchenko, V. Latora, et al. Detection of complex networks modularity by dynamical clustering. Physical Review E,75:045102,2007.
[81]A. Clauset, M. E. J. Newman, C. Moore. Finding community structure in very large networks. Physical Review E,70:066111,2004.
[82]J. Duch, A. Arenas. Community detection in complex networks using extremal optimization. Physical Review E,72:027104,2005.
[83]M. Young, J. Saner, G. Csdrdi. An agent-based algorithm for detecting commu-nity structure in networks. cond-mat/0408263.
[84]S. Fortunato, M. Barthelemy. Resolution limit in community detection. Pro-ceedings of the National Academy of Science of the USA(PNAS),104(1):36-41, 2007.
[85]J. P. Bagrow, E. M. Bollt. Local method for detecting communities. Physical Review E,72:046108,2005.
[86]A. Clauset. Finding local community structure in networks. Physical Review E, 72:026132,2005.
[87]J. P..Bagrow. Evaluating local community methods in networks. Journal of Statistical Mechanics:Theory and Experiment, P05001,2008.
[88]D. B. Vincent, et al. Fast unfolding of communities in large networks. Journal of Statistical Mechanics:Theory and Experiment, page P10008,2008.
[89]S. Muff, F. Rao, A. Caflisch. Local modularity measure for network clusteriza-tions. Physical Review E,72:056107,2005.
[90]Z. Li, S. Zhang, R. S. Wang, et al. Quantitative function for community detection. Physical Review E,77:036109,2008.
[91]J. M. Kumpula, J. Saramaki, K. Kaski, et al. Limited resolution and multiresolu-tion methods in complex network community detection. Fluctuation and Noise Letters,7:209-214,2007.
[92]D. Hristo. A scalable multilevel algorithm for graph clustering and community structure detection. WAW, pages 117-128,2006.
[93]A. Arenas, A. Fernandez, S. Gomez. Multiple resolution of the modular structure of complex networks. New Journal of Physics,10:05039,2008.
[94]G. Yan, T. Zhou, B. Hu, et al. Efficient routing on complex network. Physical Review E,73:046108,2006.
[95]N. A. Alves. Unveiling community structures in weighted networks. Physical Review E,76:036101,2007.
[96]I. Farkas, G. Palla, T. Vicsek. Weighted network modules. New Journal of Physics,9(6):180-198,2007.
[97]S. H. Zhang, R. S. Wang, X. S. Zhang. Identification of overlapping commu-nity structure in complex networks using fuzzy c-means clustering. Physica A, 374:483-490,2007.
[98]S. H. Zhang, R. S. Wang, X. S. Zhang. Uncovering fuzzy community structure in complex networks. Physical Review E,76:046103,2007.
[99]M. Rosvall, C. T. Bergstrom. An information-theoretic framework for resolving community structure in complex networks. Proceedings of the National Academy of Science of the USA(PNAS),104(18):7327-7331,2007.
[100]S. Boettcher, A. G. Percus. Optimization with extremal dynamics. Physical Review Letter,86:5211-5214,2001.
[101]S. Boettcher, A. G. Percus. Extremal optimization for graph partitioning. Phys-ical Review E,64:026114,2001.
[102]A. J. Enright, C. A. Ouzounis. Biolayout-an automatic graph layout algorithm for similarity visualization. Bioinformatics,17(9):853-854,2001.
[103]W. W. Zachary. An information flow model for conflict and fission in small groups. Journal of Anthropological Research,33:452-473,1977.
[104]M. E. J. Newman. The structure and function of complex networks. Society for Industrial and Applied Mathematics (SIAM) Review,45:167-256,2003.
[105]R. Guimera, L. Danon, A. Diaz-Guilera, et al. Self-similar community structure in a network of human interactions. Physical Review E,68:065103,2003.
[106]T. Roxborough, A. Sen. Graph clustering using multiway ratio cut. Proceedings of Graph Drawing Symposium,1353:291-296,1997.
[107]J. Shi, J. Malik. Normalized cuts and image segmentation. IEEE Trans on Pattern Analysis and Machine Intelligence,22(8):888-905,2000.
[108]I. Dhillon, Y. Guan, B. Kulis. A unified view of kernel k-means, spectral clustering and graph cuts. Technical Report UTCS-TR-04-25,2004.
[109]L. Danon, A. Diaz-Guilera, J. Duch, et al. Comparing community structure identification. Journal of Statistical Mechanics:Theory and Experiment, page P09008,2005.
[110]S. Fortunato, C. Castellano. Community detection in graphs. http://arxiv.org/abs/0712.2716,2007.
[111]Y. Fan, et al. Accuracy and precision of methods for community identification in weighted networks. Physica A,377:363-372,2007.
[112]T. Heimo, J. M. Kumpula, K. Kaski, et al. Detecting modules in dense weighted networks with the potts method. Journal of Statistical Mechanics:Theory and Experiment, page P08007,2008.
[113]J. M. Kumpula, J. Saramaki, K. Kaski, et al. Limited resolution in complex network community detection with potts model approach. European Physical Journal B,56:41-45,2007.
[114]A. Lancichinetti, S. Fortunato, F. Radicchi. Benchmark graphs for testing com-munity detection algorithms. Physical Review E,78:046110,2008.
[115]J. Shawe-Taylor, N. Cristianini. Kernel methods for pattern analysis. Cambridge University Press,2004.
[116]F. Fouss, L. Yen, A. Pirotte, et al. An experimental investigation of graph kernels on a collaborative recommendation task. Sixth IEEE International Conference on Data Mining (ICDM'06), pages 863-868,2006.
[117]B. J. Frey, D. Dueck. Clustering by passing messages between data points. Sci-ence,315(5814):972-976,2007.
[118]L. Wang, C. Leckie, K. Ramamohanarao, et al. Automatically determining the number of clusters in unlabeled data sets. IEEE Transactions on Knowledge and Data Engineering.,21(3):335-350,2009.
[119]王开军,张军英,李丹,et al.自适应仿射传播聚类.自动化学报,33(12)：1242-1246,2007.
[120]R. I. Kondor, J. Lafferty. Diffusion kernels on graphs and other discrete struc-tures. Proceedings of the 19th International Conference on Machine Learn-ing(ICML), page 315-322,2002.
[121]A. J. Smola, R. I. Kondor. Kernels and regularization on graphs. Proceedings of the Conference on Learning Theory (COLT) and Kernels Workshop, pages 144-158,2003.
[122]F. Fouss, A. Pirotte, J. M. Renders, et al. Random-walk computation of similari-ties between nodes of a graph, with application to collaborative recommendation. IEEE Transactions on Knowledge and Data Engineering,19(3):355-369,2007.
[123]S. Lafon, A. B. Lee. Diffusion maps and coarse-graining:A unified framework for dimensionality reduction. IEEE Transactions on Pattern Analysis and Machine Intelligence,28(9):1393-1403,2006.
[124]B. Nadler, S. Lafon, R. Coifman, et al. Diffusion maps, spectral clustering and eigenfunctions of fokker-planck operators. Advances in Neural Information Pro-cessing Systems,18:955-962,2006.
[125]S. Zhang, X. M. Ning, X. S. Zhang. Graph kernels, hierarchical clustering, and network community structure:experiment and comparative analysis. European Physical Journal B,68:065103,2003.
[126]E. Leicht, P. Holme, M. E. J. Newman. Vertex similarity in networks. Phys. Rev. E,73(2):026120,2006.
[127]http://www.mathworks.com/matlabcentral/fileexchange/authors/24811.
[128]http://www personal.umich.edu/-mejn/.
[129]V. L. R, D. L. W. Graphsplatting:Visualizing graphs as continuous fields. IEEE Transactions on Visualization and Computer Graphics,9(2):206-212,2003.
[130]C. Li, P. K. Maini. An evolving network model with community structure. Jour-nal of Physics A:Mathematical and General,38:9741-9749,2005.
[131]M. E. J. Newman. Detecting community structure in networks. European Phys-ical Journal B,38(2):321-330,2004.
[132]J. Karhunen, J. Joutsensalo. Generalizations of principal component analysis, optimization problems, and neural networks. Neural Networks,8(4):549-562, 1995.
[133]V. C. Klema. The singular value decomposition:Its computation and some application. IEEE Transaction on Automatic Control, pages 164-176,1980.
[134]T. F. Cox, M. A. A. Cox. Multidimensional Scaling. Chapman and Hall, New York,2000.
[135]S. T. Roweis, L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science,290(5500):2323-2326,2000.
[136]J. B. Tenenbaum, V. d. Silva, J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science,290(12):2319-2323,2000.
[137]曾宪华.流形学习的谱方法相关问题研究[博士论文].北京交通大学计算机与信息技术学院,2009.
[138]F. J. Brandenburg, M. Himsolt, C. Rohrer. An experimental comparison of force-directed and randomized graph drawing algorithms. Proc. Symposium on Graph Drawing (LNCS),1027:76-87,1996.
[139]U. Brandes, S. Cornelsen. Visual ranking of link structures. Proc.7th Inter-national Workshop on Algorithms and Data Structures (WADS),2125:222-233, 2001.
[140]A. Noack. An energy model for visual graph clustering. In Proc.11th Interna-tional Symposium on Graph Drawing,2912:425-436,2004.
[141]D. Auber, Y. Chiricota, F. Jourdan, et al. Multiscale visualization of small world networks. In Proceedings of the 2003 IEEE Symposium on Information Visual-ization, pages 75-81,2003.
[142]J. C Bezdek, R. J. Hathaway. Vat:A tool for visual assessment of (cluster) tendency. Proc. Int'l Joint Conf. Neural Networks (IJCNN'02), pages 2225-2230,2002.
[143]S. Yang, S. Luo, J. Li. A novel visual clustering algorithm for finding community in complex network. International Conference on Advanced Data Mining and Applications(ADMA),4093:396-403,2006.
[144]M. Molloy, B. Reed. A critical point for random graphs with a given degree sequence. Random Structures and Algorithms,6:161-180,1995.
[145]A. L. N. Fred, A. K. Jain. Robust data clustering. IEEE Computer Society Conference on Computer Vision and Pattern Recognition(CVPR),1:128-133, 2003.
[146]L. I. Kuncheva, S. T. Hadjitodorov. Using diversity in cluster ensembles. IEEE International Conference on Systems, Man and Cybernetics,2:1214-1219,2004.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |