基于复杂网络的拓扑与信息传输问题研究
|
摘要
网络动力学的研究主要包括网络演化机制以及网络行为两个方面。根据最新的研究成果表明,大量的真实网络如Internet、WWW等既不是纯粹的规则网络也不是完全的随机网络,而是介于确定性与随机性之间的复杂网络。此前,有关网络动力学的研究是建立在确定的规则网络或是随机的均匀网络基础上的,因此有些结论在复杂网络中并不一定成立。本文汲取了复杂网络研究的最新成果对信息网络的演化机制及传输行为进行了研究,主要贡献如下:
1.提出了“基于Agent的信息网络演化模型”,设计了新的网络演化机制并通过迭代的方式生成了该模型的拓扑结构。相对于其它网络演化模型,该模型不仅将“小世界特性”、“无标度特性”、“高聚类特性”以及“社团性”纳入到同一框架内,而且还可以通过调节演化参数来控制网络的拓扑演化进程。
2.将模拟退火算法应用于社团划分并提出了“基于节点类型的网络社团划分算法”。该算法的基本思想是首先将原始网络随机地划分为若干社团,然后根据初始划分后的结果对各社团内部的节点以及社团间节点的连接方式进行分类,根据分类结果对网络进一步进行划分,直到满足最优化条件。最后通过实验将该算法与模拟退火算法以及GN算法进行了比较,实验结果表明该算法能够有效、准确地对网络社团结构进行划分。
3.定量地研究了网络“平均度”、“无标度特性”、“小世界特性”以及“社团性”对信息传输能力产生的影响。实验发现,(1)随着网络平均度的逐渐增大,网络的传输能力逐渐增强;(2)在网络平均度一定的情况下,随着长程连接的逐渐增多,网络的传输能力开始由弱变强,然后由强变弱;(3)随着幂指数γ的值的不断增加,网络的临界相变点都在逐渐减小。(4)网络社团性越强,传输能力越弱,反之亦然。
4.推导出了一般路由行为下网络临界相变点的计算公式;通过实验和理论证明了在节点传输能力一定的情况下ω=-1对应的基于节点连接度的局部路由策略表现最优以及节点传输能力不定的情况下ω=1、对应局部路由策略最优;提出了根据节点“有效介数”进行选路的路由策略。实验结果表明,β=1对应的路由算法表现最优且基于节点有效介数的路由策略普遍要比基于节点连接度的路由策略表现更好。
The studies on network dynamics can be divided into two groups: the evolution mechanisms of networks and the behavior on networks. According to the latest studies, many real networks such as Internet、WWW etc are not complete regular networks or random networks, on the contrary, they are complex networks that both have certainty and uncertainty. Therefore, those conclusions that based on random networks or regular networks may not apply to complex networks. In this paper, the studies mainly focus on the evolution mechanisms of networks and information transmission problems based on the latest research on complex networks
1. A new evolving network model named“the information transmission model based on agent”is proposed. New evolution mechanisms are designed by summarizing the common topological properties of information networks and by using the methord of network dynamics theory for reference. Compared to other models, this model could not only incorporate small-world property, scale-free property and community property into the same framework but also control the evolution process of network by adjusting the parameters.
2. SA algorithm is applied to find community structure of networks and a new algorithm that based on the roles of nodes (PANT) in complex networks is proposed for the same purpose. The basic idear of PANT algorithm is as follows: Firstly, stochastic algorithm is adopted for initial partition. Then, nodes are classified into four different types and the connections between different communities are classified into three types. According to different types of connctions, further partitions of the network are made until the algorithm reaches optimization. Experimental results show that this algorithm could find the community structure efficiently.
3. How topological properties of complex networks such as small-world property, scale-free property and community property affect the transmission capacity of a network are studied. Experimental results show that (1) as the average degree of the a network increases, the transmisison capacity of a network increases either (2) when the average degree of a network keeps unchanged, as the number of long-range connections increases, the capacity of a network increases at first and then decreases when the quantity of long-range connections is much more than local conncetions.(3) when exponentialγincreases, the capacity decreases.(4) the stronger the modularity is , the lower efficiency the transmission capacity has.
4. It is found thatω=-1 responds to the optimal local routing strategy when the capacity of each node is a constant andω=1 responds to the best local routing strategy when the capacity of each node is not a constant. In order to further maximize the capacity of the network, a glocal routing strategy based on“effective betweenness”is proposed. Experimental results show thatβ=1 responds to the best routing strategy and routing strategies based on effevtive betweenness run better than those routing algorithms based on the degree of nodes.
1.提出了“基于Agent的信息网络演化模型”,设计了新的网络演化机制并通过迭代的方式生成了该模型的拓扑结构。相对于其它网络演化模型,该模型不仅将“小世界特性”、“无标度特性”、“高聚类特性”以及“社团性”纳入到同一框架内,而且还可以通过调节演化参数来控制网络的拓扑演化进程。
2.将模拟退火算法应用于社团划分并提出了“基于节点类型的网络社团划分算法”。该算法的基本思想是首先将原始网络随机地划分为若干社团,然后根据初始划分后的结果对各社团内部的节点以及社团间节点的连接方式进行分类,根据分类结果对网络进一步进行划分,直到满足最优化条件。最后通过实验将该算法与模拟退火算法以及GN算法进行了比较,实验结果表明该算法能够有效、准确地对网络社团结构进行划分。
3.定量地研究了网络“平均度”、“无标度特性”、“小世界特性”以及“社团性”对信息传输能力产生的影响。实验发现,(1)随着网络平均度的逐渐增大,网络的传输能力逐渐增强;(2)在网络平均度一定的情况下,随着长程连接的逐渐增多,网络的传输能力开始由弱变强,然后由强变弱;(3)随着幂指数γ的值的不断增加,网络的临界相变点都在逐渐减小。(4)网络社团性越强,传输能力越弱,反之亦然。
4.推导出了一般路由行为下网络临界相变点的计算公式;通过实验和理论证明了在节点传输能力一定的情况下ω=-1对应的基于节点连接度的局部路由策略表现最优以及节点传输能力不定的情况下ω=1、对应局部路由策略最优;提出了根据节点“有效介数”进行选路的路由策略。实验结果表明,β=1对应的路由算法表现最优且基于节点有效介数的路由策略普遍要比基于节点连接度的路由策略表现更好。
The studies on network dynamics can be divided into two groups: the evolution mechanisms of networks and the behavior on networks. According to the latest studies, many real networks such as Internet、WWW etc are not complete regular networks or random networks, on the contrary, they are complex networks that both have certainty and uncertainty. Therefore, those conclusions that based on random networks or regular networks may not apply to complex networks. In this paper, the studies mainly focus on the evolution mechanisms of networks and information transmission problems based on the latest research on complex networks
1. A new evolving network model named“the information transmission model based on agent”is proposed. New evolution mechanisms are designed by summarizing the common topological properties of information networks and by using the methord of network dynamics theory for reference. Compared to other models, this model could not only incorporate small-world property, scale-free property and community property into the same framework but also control the evolution process of network by adjusting the parameters.
2. SA algorithm is applied to find community structure of networks and a new algorithm that based on the roles of nodes (PANT) in complex networks is proposed for the same purpose. The basic idear of PANT algorithm is as follows: Firstly, stochastic algorithm is adopted for initial partition. Then, nodes are classified into four different types and the connections between different communities are classified into three types. According to different types of connctions, further partitions of the network are made until the algorithm reaches optimization. Experimental results show that this algorithm could find the community structure efficiently.
3. How topological properties of complex networks such as small-world property, scale-free property and community property affect the transmission capacity of a network are studied. Experimental results show that (1) as the average degree of the a network increases, the transmisison capacity of a network increases either (2) when the average degree of a network keeps unchanged, as the number of long-range connections increases, the capacity of a network increases at first and then decreases when the quantity of long-range connections is much more than local conncetions.(3) when exponentialγincreases, the capacity decreases.(4) the stronger the modularity is , the lower efficiency the transmission capacity has.
4. It is found thatω=-1 responds to the optimal local routing strategy when the capacity of each node is a constant andω=1 responds to the best local routing strategy when the capacity of each node is not a constant. In order to further maximize the capacity of the network, a glocal routing strategy based on“effective betweenness”is proposed. Experimental results show thatβ=1 responds to the best routing strategy and routing strategies based on effevtive betweenness run better than those routing algorithms based on the degree of nodes.
引文
[1] Faloutsos, Faloutsos et al, On Power-Law Relationships of The Internet Topology, ACM SIG-COMM,1999
[2] R Pastor-Satorras, A Vázquez, A Vespignani,Dynamical and Correlation Properties of The Internet,Physical Review Letters, 2007
[3] H Tangmunarunkit, R Govindan, S Shenker et al,The Impact of Routing Policy on Internet Paths, IEEE INFOCOM,2001
[4] A Fox, EA Brewer,Reducing WWW Latency and Bandwidth Requirements by Real-Time Distillation,Computer Networks and ISDN Systems,2008
[5]S.Brin, L.Page.The anatomy of a large-scale hypertextual Web search engine.In: Proceedings of 7th International World Wide Web Conference. Brisbane, Australia, 1998, 107~117
[6]J.Cho.Crawling the Web: Discovery and maintenance of large-scale Web data. PhD Dissertation, Stanford University, California, 2007
[7]祝滨,仇晋,基于矢量坐标搜索法的地区电网网络拓扑方法的研究,电力自动化设备,2006
[8]曹一家,陈晓刚,孙可,基于复杂网络理论的大型电力系统脆弱线路辨识,电力自动化设备,2006
[9]龙启峰,陈岗,丁晓群,电力系统网络拓扑分析的有色Petri网模型,电网技术,2000
[10]欧海涛,张卫东,基于多智能技术的城市智能交通控制系统,电子学报,2000
[11]李明利,赵祥模,王选民,分组拥塞控制在城市交通控制中的应用,自然科学报,2009
[12]苏兵,徐寅峰,交通网络的抗堵塞能力分析与计算,系统工程,2008
[13] AL Barabasi, H Jeong, Z Neda et al,Evolution of the social network of scientific collaborations,Physica A: Statistical,2006
[14]LAN Amaral,A Scala,M Barthelemy et al,Classes of Small-World Networks,Pcoceedings of the National Academy Sciences,2000,97(21):11149~11152
[15]MEJ Newman,The Structure of Scientific Collaboration Networks,Reviews of Modern Physics,2002
[16]S Boccaletti,V Latora,Y Moreno et al,Complex Networks: Structure and Dynamics,Physics Reports, 2006
[17]J.Kubiatowicz, W.Weimer, C.Wells et al.OceanStore: an architecture for global-scale persistent storage. In:ACM SIGPLAN Notices,ACM Press, New York,USA., 2007, 35(11):190~201
[18]D.S.Milojicic, V.Kalogeraki, R.Lukose et al.Peer-to-peer computing, Tech Report: HPL-2002-57, http://www.hpl.hp.com/techreports/2002/HPL-2002-57.pdf,2002
[19] S.Ratnasamy, P.Francis, M.Handley.A scalable content-addressable network.In:Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communications,San Diego, California, USA,2001,161~172
[20]卢开澄,卢华明,图论及其应用,北京:清华大学出版社,2005,221~250
[21]Martin, Charles, Golumbic, Algorithmic Graph Theory and Perfect Graphs, http://www.google.com/books?hl=zh-CN&lr=&id=8xo-VrWo5_QC&oi=fnd&pg=PR13&dq=Graph+Theory&ots=brp0nKqp80&sig=hgPwU6bTUV2r_SK6Sdrb2tmEvfQ#v=onepage&q&f=false,2009
[22]CD Godsil, G Royle, Algebraic Graph Theory, Springer Verlag, 2008, 78~112
[23]Béla Bollobás,Modern Graph Theory, http://www.google.com/books?hl=zh-CN&lr=&id=SbZKSZ-1qrwC&oi=fnd&pg=PR7&dq=Graph+Theory&ots=NzAxjcq4A1&sig=N6jbkrfbq14GZkcet1WWLViUhBg#v=onepage&q&f=false,1998,117~130
[24]I.Stoica, R.Morris, D.Karger et al.Chord: A scalable peer-to-peer lookup service for internet applications.In: Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communications. San Diego, California, USA, 2001, 149~160
[25]徐俊明,图论及应其用,北京:中国科学技术大学出版社,1998,230~354
[26] AV Goldberg, C Harrelson,Computing the Shortest Path: A Search Meets Graph Theory,Proceedings of The Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms,2007,156~165
[27]Philip Klein, Preprocessing an undirected planar network to enable fast approximate distance queries, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, 2002,820~828
[28]汪小帆,李翔,陈关荣,复杂网络理论及其研究,北京:清华大学出版社,2005,30~38
[29]P Erdos, A Renyi, On The Evolution of Random Graphs,Publ.Math.Inst.Hung.Acad.Sci.,1960,5:17~60
[30] Béla Bollobás,Random Graphs,http://www.google.com/books?hl=zh-CN&lr=&id=o9WecWgilzYC&oi=fnd&pg=PR10&dq=related:enKaHUGZeNYJ:scholar.google.com/&ots=YyKMrVUrSl&sig=agUv-JcYzFKoyVTglbZEcQyPQRk#v=onepage&q&f=false,2001,15~60
[31]R Guimera, S Mossa,A Turtschi,The worldwide Air Transportation Netork:Anomalous Centrality, Community Structure, and Cities Global Roles,Proc.Natl.Acad.Sci,2008,102(22):7749~7799
[32]R Albert, A L Barabasi,Topology of Evolving networks,Phys.Rev.Lett,2000,85:5234~5237
[33]L A N Amaral,J M Ottino,Complex Networks:Augmenting The Framework for The Study of Complex Systems,The European Physical Journal B,2004,38:147~162
[34]D J Watts, The New Science of Networks,Annual Review of Sociology,2004,30:243~270
[35]D J Watts,S H Strogatz,Collective Dynamics of‘Small World’Networks,Nature,1998,393(6684):440~442
[36]A.Vazquez, Pastor Satorras, A.Vespignani, Internet Topology at The Router and Autonomous System Level, arXiv:cond-mat/0206804,2002,1(6)
[37]A L Barabasi, R Albert, Emergence of Scaling in Random Networks, Science, 1999, 286(5439):509~512
[38]R Albert,H Jeong,A L Barabasi,Diameter of the Word Wide Web,Nature,1999,401:130~131
[39]吴金闪,狄增加,从统计物理学看复杂网络的研究,南京:物理学进展,2004,24(1):19~46
[40]M,Girvan, M E J Newman,Community Structure in Social and Biological Network,Proc.Nat1.Acad.Sci,2002,99(12):7821~7826
[41]D Gibson, J Kleinberg, P Raghavan, Inferring Web Communities from Link Topology, Proceedings of The 9th ACM Conference on Hypertext and Hypermedia, 1998,225~234
[42]W W Zachary, An Information Flow Model for Conflict and Fission in Small Groups,Journal of Anthropological Research ,1997,33:452~473
[43]J Duch, A Arenas, Community Detection in Complex Networks Using Extreme Optimization,Phys Rev E,2007,70(6):066111
[44]K L Calvert, M B Doar,E Zegura,Modeling Internet Topology,IEEE Communication Magazine,1997,35(6):160~163
[45] M,Faloutsos, P Faloutsos,C Faloutsos, On Power-Law Relationships of The Internet Topology,Comput.Commun.Rev,2009
[46]T Bu,D Towsley,On Distinguishing between Internet Power Law Topology Generators,In Proc.of the IEEE INFOCOM 2002,2:~638~647
[47]EM Jin, M Girvan, MEJ Newman, Structure of Growing Social Networks, Physical Review E,2001
[48]X Li, G Chen,A Local-World Evolving Network Model,Physica A:Statistical Mechanic and Its Applications,2003
[49]宋莉雅,李翔,汪小帆,互联网的局域世界演化模型仿真研究,计算机仿真,2006
[50]G Palla, I Derényi, I Farkas,Uncovering The Overlapping Community Structure of Complex Networks in Nature and Society,Nature,2005
[51]MEJ Newman,Detecting Community Structure in Networks,The European Physical Journal B-Condensed Matter,2004
[52]A Clauset, MEJ Newman, C Moore, Finding Community Structure in Very Large Networks, 2004
[53]J Duch, A Arenas, Community Detection in Complex Networks Using Extremal Optimization, Physical Review E, 2005
[54]刘婷,胡宝清,基于聚类分析的复杂网络中的社团探测,复杂系统与复杂性科学,2008
[55]RL Breiger , Toward An Operational Theory of Community Elite Structure,Quality and Quantity 1979
[56]MEJ Newman, M Girvan, Finding and Evaluating Community Structure in Networks, Physical Review E, 2004
[57]BW Kernighan, S Lin, An Efficient Heuristic Procedure for Partition Graphs, 1970
[58]杨建新,周献中,葛银茂,基于拉普拉斯图谱和K均值的多社团发现方法,计算机工程,2008
[59]朱大勇,侯晓荣,张新丽,遗传聚类的社团结构发现,智能系统学报,2009
[60]X Liu,D Y Li,S L Wang,Effectvie Algorithm for Detecting Community Structure in Complex Networks Based on GA and Clustering,Computer Science,2007,4488:657~664
[61]M Tasgin,A Herdagdelen,H Bingol,Community Detection in Complex Networks Using Genetic Algotithms, http://arxiv.org/abs/0711.0491,2008
[62]M.Li, W.C.Lee, A.Sivasubramaniam et al.A small world overlay network for semantic based search in P2P systems.In: Proceedings of Workshop on Semantics in Peerto-Peer and Grid Computing (SemPGrid), in conjunction with the World Wide Web Conference (WWW), 2004
[63]M.Li, W.C.Lee, A.Sivasubramaniam et al.Semantic small world: an overlay network for peer-to-peer search.In: Proceedings of the 12th IEEE International Conference on Network Protocols, 2004, 228~238
[64]V Paxson,End-to-End Routing Behavior in The Internet,ACM SIGCOMM Computer Communication Review,2008
[65]C Labovitz, GR Malan, F Jahanian, Internet Routing Instability, IEEE/ACM Transaction on Networking, 1998
[66]R Govindan, A Reddy, An Analysis of Internet Inter-domain Topology and Route Stability, 1997
[67]HX Ge, SQ Dai, LY Dong, Y Xue,Stabilization Effect of Traffic Flow in An Extended Car-Following Model
[68]T Litman, Measuring Transportation-Traffic, Mobility and Accessibility, 2009 http://elibrary.ru/item.asp?id=6232654
[69]DJ Watts, PS Dodds, MEJ Newman, Identity and Search in Social Networks, Science, 2002
[70]R Guimera, A Arenas, A Díaz-Guilera, Dynamical Properties of Model Communication Networks, Physics Review Letter, 2002
[71]A Arenas, A Diaz-Guilera, R Guimera, Communication in Networks with Hierarchical Branching, Physical Review Letters, 2001
[72]G Yan, T Zhou, B Hu, Efficient Routing on Complex Networks, Physical Review E, 2006
[73]Z Chen, X Wang, Effects of Network Capacity under Variations of Network Structure and Routing Strategy, Networking, Sensing and Control, 2007
[74]J Duch, A Arenas, Community Detection in Complex Networks Using Extrmal Optimization, Physical Review E, 2008
[75]N Christofides, Graph Theory: An Algorithmic Approach (Computer Science and Applied Mathematics),1975
[76]J L Gross, T W Tucker, Topological Graph Theory, http://www.google.com/books?hl=zh-CN&lr=&id=mrv9OJVdy_cC&oi=fnd&pg=PA1&dq=Graph+theory&ots=MXKxRtofY8&sig=bczKyaJXVfBXGOhKd1m7hXt5XMM#v=onepage&q&f=false, 2001
[77]郑海,张国清,物理网络拓扑发现算法的研究,计算机研究与发展,2002
[78]吴君青,陈卫卫,胡谷雨,物理网络拓扑发现算法的研究与改进,北京邮电大学学报,2003
[79]王志刚,王汝传,王绍棣,网络拓扑发现算法的研究,通信学报,2004
[80]刘涛,陈忠,陈晓荣,复杂网络理论及其应用研究概述,系统工程,2009
[81]B.BollobAs,Random Graphs,Academic Press, 1985
[82] H.Kautz, B.Selman, M.Shah.ReferralWeb: Combining Social Networks and Collaborative Filtering.Communications of the ACM, March 1997, 40(3):63~65
[83] P.Erdos, A.Renyi.On the evolution of random graphs.Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 1960, 5:17~61
[84]P.Erdos, A.Renyi.On random graphs.Publicationes Mathematicae, 1959, 6:290~297
[85]D.J.Watts, S.H.Strogatz.Collective Dynamics of Small-World Networks.Nature, 1998, 393:440~442
[86]M.E.J. Newman,D.J.Watts.Scaling and percolation in the small-world network model.Physical Review, 1999, E 60:7332~7342
[87]R Albert, AL Barabási, Statitical Mechanics of Complex Netwoks, 2002
[88]AL Barabasi,Linked: How Everything Connected to Everything Else and What It Means, http://0-ems.wcu.edu.wncln.wncln.org/20041227.pdf, 2003
[89]R Albert, AL Barabasi Topology of evolving networks: local events and universality, Physical review letters,2000
[90]L.A.N. Amaral, A.Scala, M.Barthklkmy et al.Classes of small-world networks, In: Proceedings of the National Academy of Sciences,2000 ,11149~11152
[91]D.J.Watts.Small Worlds: The Dynamics of Networks Between Order and Randornness.Princeton University Press, Princeton, New Jersey, 1999.
[92] A.Barrat, M.Weigt.On the properties of small-world network models The European Physical Journal B - Condensed Matter and Complex Systems,2000, 13(3):547~560
[93]M.E.J.Newman, D.J.Watts.Renormalization group analysis of the small-world network model.Physics Letters A, 1999, 263(4-6):341~346
[94]廖守亿,戴金海,复杂适应系统及基于Agent的建模与仿真方法,系统仿真学报,2004
[95]P Gleiser, L Danon, Community structure in Jazz, Advances in Complex Systems, 2003,6:565~573
[96]A Pothen, H simon, K P Liou, Partitioning Sparse Matrices with Eigenvectors of Graphs, SIAM J.Matrix Anal. Appl,1990,11:430
[97]R Milo, Network Motifs: Simple Building Blocks of Complex Networks, Scinece,2008,298:824
[98]A L Admic, E Adar, Friends and Neighbors on The Web Social Networks,2003,25:211~230
[99]G W Flake, S R Lawrence, C L Giles, Self-organization and Identification of Web Communities,IEEE Computer,2008,35:66~71
[100]M.E.J.Newman.The structure and function of networks.SIAM Review, 2007, 45(2):167~256
[101]R.Baeza-Yates, B.Ribeiro-Neto, Mordern Information Retrieval(王知津等译),北京:机械工业出版社,2007.
[102]S.E.Robertson, K.S.Jones.Relevance weighting of search terms.Journal of the American Society for Information Science, 1976, 27(3):129~146
[103]G.Salton, M.McGill.Introduction to Modern Information Retrieval.McGraw-Hill, NewYork, 1983
[104]王雪梅,王义和,模拟退火算法与遗传算法的结合,计算机学报,1997
[105]康立山,谢云,尤矢勇,模拟退火算法, ftp://202.118.239.46/Incoming%2FeBook%2F%C4%A3%C4%E2%CD%CB%BB%F0%CB%E3%B7%A8.pdf,1994
[106]G.Karypis, V.Kumar.Multilevel k-way hypergraph partitioning.In: Proceedings of the Design and Automation Conference, 2009, 243~348
[107]W.M.Shaw, R.Burgin, P.Howell.Performance standards and evaluations in IR test collections: Cluster-based retrieval models. Information Processing and Management, 1997, 33(1):1~14
[108]C.Schmitz.Self-organization of a Small World by Topic.In: Proceedings of First International Workshop on Peer-to-Peer Knowledge Management, Boston, MA, August 2004.
[109]L.Guo, S.Jiang, L.Xiao et al.Exploiting Content Localities for Efficient Search in P2P Systems.In:Proceedings of 18th International Symposium on Distributed Computing (DISC 2004), Amsterdam, Netherlands, LNCS, 2007, 3274:349~364
[110]T.Bonald, A.Proutiere,J.W Roberts,Statistical Performance Guarantees for Streaming Flows Using Expedited Forwarding,Proc.IEEE INFOCOM,2001,1104~1112
[111]T.Bonald, J Roberts,Congestion at Flow Level and The Impact of User Behavior,Comput.Netw,2003,42:521~536
[112]B Suter,T V Lakshman,D stiliadis,Buffer Management Schemes for Supporting TCP in Gigabit Routers with Per-flow Queueing,IEEE J.Select.Areas Commun,1999,17:1159~1170
[113]U Black, IP Routing Protocols: RIP, OSPF, BGP, PNNI and Cisco Routing Protocols, http://portal.acm.org/citation.cfm?id=331258, 2009
[114]J Pu, E Manning, GC Shoja, A Srinivasan, A New Algorithm to Compute Alternate Paths in Reliable OSPF (ROSPF),Internet Conference on Computer,2001
[115]M.Jovanovic, F.S.Annexstein, K.A.Berman.Modeling peer-to-peer network topologies through small-world models and power laws.IX Telecommunications Forum TELFOR, 2009, 20~22
[116]D Comer, Internetworking with TCP/IP: principles, protocols, and architecture, http://www.google.com/books?hl=zh-CN&lr=&id=jonyuTASbWAC&oi=fnd&pg=PR23&dq=RIP+OSPf&ots=i3ZhR6ZPZq&sig=Z6RJ4g7ri71Gery-wbfM_SS90WA, 2006
[117]M.Faloutsos, P.Faloutsos, C.Faloutsos.On power-law relationships of the Internet topology.In:Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication,1999, 251~262
[118]JM Kleinberg, Navigation in a small world, Nature, 2000
[119]S.Bordag,G.Heyer,U. Quasthoff.Small worlds of concepts and other principles of semantic search.In:Proceedings of Innovative Internet Computing Systems Second International Workshop (IICS),LNCS,2003,2877:10~19
[120]Z.Xu, R.Min, Y.Hu.Reducing maintenance overhead in DHT based peer-to-peer algorithms.In: Proceedings of Third International Conference on Peer-to-Peer Computing, 2003, 218~219
[121]B Awerbuch, A Bar-Noy, M Gopal, Approximate Distributed Bellman-ford Algorithms, IEEE Transactions on Communications,1994
[122]A.B.Teslyuk, S.A.Krashakov, L.N.Shchur.On the universality of rank distributions of website popularity.Computer Networks, 2006,50(11): 1769~1780
[123]Oskar Sandberg.Searching in a Small World.[Doctor Dissertation], Goteborg University,Goteborg, Sweden, 2008,14~15
[124]P Echenique,J Gomez-Gardenes,Y Moreno, Improved Routing Strategies for Internet Traffic Delivery, Physical Review E,2004
[125]P Echenique,J Gomez-Gardenes,Y Moreno, Dynamics of Jamming Transitions in Complex Networks, Europhysics Letters,2005,71:325
[126]P Echenique,J Gomez-Gardenes,Y Moreno, Distance-d Covering Problems in Scale-free Networks with Degree Correlations,2004,70:056105
[127]Y Moreno,R Pastor-Satorras,A Vazquez, Epidemic Outbreaks in Complex Heterogeneous Networks, The European Physical Letters,2006
[128]L.A.Adamic, R.M.Lukose, A.R.Puniyani et al.Search in power-law networks.Physical Review, 2009, E64:046135
[129]B Brand, Method to Route A Network Nnitiated Message in A Complex Network Using Radius Protocol,http://www.freepatentsonline.com/EP1909450.html, 2008
[130]Ulric, A Fast Algorithm for Betweenness Centrality , Journal of Mathematical Sociology,2005
[2] R Pastor-Satorras, A Vázquez, A Vespignani,Dynamical and Correlation Properties of The Internet,Physical Review Letters, 2007
[3] H Tangmunarunkit, R Govindan, S Shenker et al,The Impact of Routing Policy on Internet Paths, IEEE INFOCOM,2001
[4] A Fox, EA Brewer,Reducing WWW Latency and Bandwidth Requirements by Real-Time Distillation,Computer Networks and ISDN Systems,2008
[5]S.Brin, L.Page.The anatomy of a large-scale hypertextual Web search engine.In: Proceedings of 7th International World Wide Web Conference. Brisbane, Australia, 1998, 107~117
[6]J.Cho.Crawling the Web: Discovery and maintenance of large-scale Web data. PhD Dissertation, Stanford University, California, 2007
[7]祝滨,仇晋,基于矢量坐标搜索法的地区电网网络拓扑方法的研究,电力自动化设备,2006
[8]曹一家,陈晓刚,孙可,基于复杂网络理论的大型电力系统脆弱线路辨识,电力自动化设备,2006
[9]龙启峰,陈岗,丁晓群,电力系统网络拓扑分析的有色Petri网模型,电网技术,2000
[10]欧海涛,张卫东,基于多智能技术的城市智能交通控制系统,电子学报,2000
[11]李明利,赵祥模,王选民,分组拥塞控制在城市交通控制中的应用,自然科学报,2009
[12]苏兵,徐寅峰,交通网络的抗堵塞能力分析与计算,系统工程,2008
[13] AL Barabasi, H Jeong, Z Neda et al,Evolution of the social network of scientific collaborations,Physica A: Statistical,2006
[14]LAN Amaral,A Scala,M Barthelemy et al,Classes of Small-World Networks,Pcoceedings of the National Academy Sciences,2000,97(21):11149~11152
[15]MEJ Newman,The Structure of Scientific Collaboration Networks,Reviews of Modern Physics,2002
[16]S Boccaletti,V Latora,Y Moreno et al,Complex Networks: Structure and Dynamics,Physics Reports, 2006
[17]J.Kubiatowicz, W.Weimer, C.Wells et al.OceanStore: an architecture for global-scale persistent storage. In:ACM SIGPLAN Notices,ACM Press, New York,USA., 2007, 35(11):190~201
[18]D.S.Milojicic, V.Kalogeraki, R.Lukose et al.Peer-to-peer computing, Tech Report: HPL-2002-57, http://www.hpl.hp.com/techreports/2002/HPL-2002-57.pdf,2002
[19] S.Ratnasamy, P.Francis, M.Handley.A scalable content-addressable network.In:Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communications,San Diego, California, USA,2001,161~172
[20]卢开澄,卢华明,图论及其应用,北京:清华大学出版社,2005,221~250
[21]Martin, Charles, Golumbic, Algorithmic Graph Theory and Perfect Graphs, http://www.google.com/books?hl=zh-CN&lr=&id=8xo-VrWo5_QC&oi=fnd&pg=PR13&dq=Graph+Theory&ots=brp0nKqp80&sig=hgPwU6bTUV2r_SK6Sdrb2tmEvfQ#v=onepage&q&f=false,2009
[22]CD Godsil, G Royle, Algebraic Graph Theory, Springer Verlag, 2008, 78~112
[23]Béla Bollobás,Modern Graph Theory, http://www.google.com/books?hl=zh-CN&lr=&id=SbZKSZ-1qrwC&oi=fnd&pg=PR7&dq=Graph+Theory&ots=NzAxjcq4A1&sig=N6jbkrfbq14GZkcet1WWLViUhBg#v=onepage&q&f=false,1998,117~130
[24]I.Stoica, R.Morris, D.Karger et al.Chord: A scalable peer-to-peer lookup service for internet applications.In: Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communications. San Diego, California, USA, 2001, 149~160
[25]徐俊明,图论及应其用,北京:中国科学技术大学出版社,1998,230~354
[26] AV Goldberg, C Harrelson,Computing the Shortest Path: A Search Meets Graph Theory,Proceedings of The Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms,2007,156~165
[27]Philip Klein, Preprocessing an undirected planar network to enable fast approximate distance queries, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, 2002,820~828
[28]汪小帆,李翔,陈关荣,复杂网络理论及其研究,北京:清华大学出版社,2005,30~38
[29]P Erdos, A Renyi, On The Evolution of Random Graphs,Publ.Math.Inst.Hung.Acad.Sci.,1960,5:17~60
[30] Béla Bollobás,Random Graphs,http://www.google.com/books?hl=zh-CN&lr=&id=o9WecWgilzYC&oi=fnd&pg=PR10&dq=related:enKaHUGZeNYJ:scholar.google.com/&ots=YyKMrVUrSl&sig=agUv-JcYzFKoyVTglbZEcQyPQRk#v=onepage&q&f=false,2001,15~60
[31]R Guimera, S Mossa,A Turtschi,The worldwide Air Transportation Netork:Anomalous Centrality, Community Structure, and Cities Global Roles,Proc.Natl.Acad.Sci,2008,102(22):7749~7799
[32]R Albert, A L Barabasi,Topology of Evolving networks,Phys.Rev.Lett,2000,85:5234~5237
[33]L A N Amaral,J M Ottino,Complex Networks:Augmenting The Framework for The Study of Complex Systems,The European Physical Journal B,2004,38:147~162
[34]D J Watts, The New Science of Networks,Annual Review of Sociology,2004,30:243~270
[35]D J Watts,S H Strogatz,Collective Dynamics of‘Small World’Networks,Nature,1998,393(6684):440~442
[36]A.Vazquez, Pastor Satorras, A.Vespignani, Internet Topology at The Router and Autonomous System Level, arXiv:cond-mat/0206804,2002,1(6)
[37]A L Barabasi, R Albert, Emergence of Scaling in Random Networks, Science, 1999, 286(5439):509~512
[38]R Albert,H Jeong,A L Barabasi,Diameter of the Word Wide Web,Nature,1999,401:130~131
[39]吴金闪,狄增加,从统计物理学看复杂网络的研究,南京:物理学进展,2004,24(1):19~46
[40]M,Girvan, M E J Newman,Community Structure in Social and Biological Network,Proc.Nat1.Acad.Sci,2002,99(12):7821~7826
[41]D Gibson, J Kleinberg, P Raghavan, Inferring Web Communities from Link Topology, Proceedings of The 9th ACM Conference on Hypertext and Hypermedia, 1998,225~234
[42]W W Zachary, An Information Flow Model for Conflict and Fission in Small Groups,Journal of Anthropological Research ,1997,33:452~473
[43]J Duch, A Arenas, Community Detection in Complex Networks Using Extreme Optimization,Phys Rev E,2007,70(6):066111
[44]K L Calvert, M B Doar,E Zegura,Modeling Internet Topology,IEEE Communication Magazine,1997,35(6):160~163
[45] M,Faloutsos, P Faloutsos,C Faloutsos, On Power-Law Relationships of The Internet Topology,Comput.Commun.Rev,2009
[46]T Bu,D Towsley,On Distinguishing between Internet Power Law Topology Generators,In Proc.of the IEEE INFOCOM 2002,2:~638~647
[47]EM Jin, M Girvan, MEJ Newman, Structure of Growing Social Networks, Physical Review E,2001
[48]X Li, G Chen,A Local-World Evolving Network Model,Physica A:Statistical Mechanic and Its Applications,2003
[49]宋莉雅,李翔,汪小帆,互联网的局域世界演化模型仿真研究,计算机仿真,2006
[50]G Palla, I Derényi, I Farkas,Uncovering The Overlapping Community Structure of Complex Networks in Nature and Society,Nature,2005
[51]MEJ Newman,Detecting Community Structure in Networks,The European Physical Journal B-Condensed Matter,2004
[52]A Clauset, MEJ Newman, C Moore, Finding Community Structure in Very Large Networks, 2004
[53]J Duch, A Arenas, Community Detection in Complex Networks Using Extremal Optimization, Physical Review E, 2005
[54]刘婷,胡宝清,基于聚类分析的复杂网络中的社团探测,复杂系统与复杂性科学,2008
[55]RL Breiger , Toward An Operational Theory of Community Elite Structure,Quality and Quantity 1979
[56]MEJ Newman, M Girvan, Finding and Evaluating Community Structure in Networks, Physical Review E, 2004
[57]BW Kernighan, S Lin, An Efficient Heuristic Procedure for Partition Graphs, 1970
[58]杨建新,周献中,葛银茂,基于拉普拉斯图谱和K均值的多社团发现方法,计算机工程,2008
[59]朱大勇,侯晓荣,张新丽,遗传聚类的社团结构发现,智能系统学报,2009
[60]X Liu,D Y Li,S L Wang,Effectvie Algorithm for Detecting Community Structure in Complex Networks Based on GA and Clustering,Computer Science,2007,4488:657~664
[61]M Tasgin,A Herdagdelen,H Bingol,Community Detection in Complex Networks Using Genetic Algotithms, http://arxiv.org/abs/0711.0491,2008
[62]M.Li, W.C.Lee, A.Sivasubramaniam et al.A small world overlay network for semantic based search in P2P systems.In: Proceedings of Workshop on Semantics in Peerto-Peer and Grid Computing (SemPGrid), in conjunction with the World Wide Web Conference (WWW), 2004
[63]M.Li, W.C.Lee, A.Sivasubramaniam et al.Semantic small world: an overlay network for peer-to-peer search.In: Proceedings of the 12th IEEE International Conference on Network Protocols, 2004, 228~238
[64]V Paxson,End-to-End Routing Behavior in The Internet,ACM SIGCOMM Computer Communication Review,2008
[65]C Labovitz, GR Malan, F Jahanian, Internet Routing Instability, IEEE/ACM Transaction on Networking, 1998
[66]R Govindan, A Reddy, An Analysis of Internet Inter-domain Topology and Route Stability, 1997
[67]HX Ge, SQ Dai, LY Dong, Y Xue,Stabilization Effect of Traffic Flow in An Extended Car-Following Model
[68]T Litman, Measuring Transportation-Traffic, Mobility and Accessibility, 2009 http://elibrary.ru/item.asp?id=6232654
[69]DJ Watts, PS Dodds, MEJ Newman, Identity and Search in Social Networks, Science, 2002
[70]R Guimera, A Arenas, A Díaz-Guilera, Dynamical Properties of Model Communication Networks, Physics Review Letter, 2002
[71]A Arenas, A Diaz-Guilera, R Guimera, Communication in Networks with Hierarchical Branching, Physical Review Letters, 2001
[72]G Yan, T Zhou, B Hu, Efficient Routing on Complex Networks, Physical Review E, 2006
[73]Z Chen, X Wang, Effects of Network Capacity under Variations of Network Structure and Routing Strategy, Networking, Sensing and Control, 2007
[74]J Duch, A Arenas, Community Detection in Complex Networks Using Extrmal Optimization, Physical Review E, 2008
[75]N Christofides, Graph Theory: An Algorithmic Approach (Computer Science and Applied Mathematics),1975
[76]J L Gross, T W Tucker, Topological Graph Theory, http://www.google.com/books?hl=zh-CN&lr=&id=mrv9OJVdy_cC&oi=fnd&pg=PA1&dq=Graph+theory&ots=MXKxRtofY8&sig=bczKyaJXVfBXGOhKd1m7hXt5XMM#v=onepage&q&f=false, 2001
[77]郑海,张国清,物理网络拓扑发现算法的研究,计算机研究与发展,2002
[78]吴君青,陈卫卫,胡谷雨,物理网络拓扑发现算法的研究与改进,北京邮电大学学报,2003
[79]王志刚,王汝传,王绍棣,网络拓扑发现算法的研究,通信学报,2004
[80]刘涛,陈忠,陈晓荣,复杂网络理论及其应用研究概述,系统工程,2009
[81]B.BollobAs,Random Graphs,Academic Press, 1985
[82] H.Kautz, B.Selman, M.Shah.ReferralWeb: Combining Social Networks and Collaborative Filtering.Communications of the ACM, March 1997, 40(3):63~65
[83] P.Erdos, A.Renyi.On the evolution of random graphs.Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 1960, 5:17~61
[84]P.Erdos, A.Renyi.On random graphs.Publicationes Mathematicae, 1959, 6:290~297
[85]D.J.Watts, S.H.Strogatz.Collective Dynamics of Small-World Networks.Nature, 1998, 393:440~442
[86]M.E.J. Newman,D.J.Watts.Scaling and percolation in the small-world network model.Physical Review, 1999, E 60:7332~7342
[87]R Albert, AL Barabási, Statitical Mechanics of Complex Netwoks, 2002
[88]AL Barabasi,Linked: How Everything Connected to Everything Else and What It Means, http://0-ems.wcu.edu.wncln.wncln.org/20041227.pdf, 2003
[89]R Albert, AL Barabasi Topology of evolving networks: local events and universality, Physical review letters,2000
[90]L.A.N. Amaral, A.Scala, M.Barthklkmy et al.Classes of small-world networks, In: Proceedings of the National Academy of Sciences,2000 ,11149~11152
[91]D.J.Watts.Small Worlds: The Dynamics of Networks Between Order and Randornness.Princeton University Press, Princeton, New Jersey, 1999.
[92] A.Barrat, M.Weigt.On the properties of small-world network models The European Physical Journal B - Condensed Matter and Complex Systems,2000, 13(3):547~560
[93]M.E.J.Newman, D.J.Watts.Renormalization group analysis of the small-world network model.Physics Letters A, 1999, 263(4-6):341~346
[94]廖守亿,戴金海,复杂适应系统及基于Agent的建模与仿真方法,系统仿真学报,2004
[95]P Gleiser, L Danon, Community structure in Jazz, Advances in Complex Systems, 2003,6:565~573
[96]A Pothen, H simon, K P Liou, Partitioning Sparse Matrices with Eigenvectors of Graphs, SIAM J.Matrix Anal. Appl,1990,11:430
[97]R Milo, Network Motifs: Simple Building Blocks of Complex Networks, Scinece,2008,298:824
[98]A L Admic, E Adar, Friends and Neighbors on The Web Social Networks,2003,25:211~230
[99]G W Flake, S R Lawrence, C L Giles, Self-organization and Identification of Web Communities,IEEE Computer,2008,35:66~71
[100]M.E.J.Newman.The structure and function of networks.SIAM Review, 2007, 45(2):167~256
[101]R.Baeza-Yates, B.Ribeiro-Neto, Mordern Information Retrieval(王知津等译),北京:机械工业出版社,2007.
[102]S.E.Robertson, K.S.Jones.Relevance weighting of search terms.Journal of the American Society for Information Science, 1976, 27(3):129~146
[103]G.Salton, M.McGill.Introduction to Modern Information Retrieval.McGraw-Hill, NewYork, 1983
[104]王雪梅,王义和,模拟退火算法与遗传算法的结合,计算机学报,1997
[105]康立山,谢云,尤矢勇,模拟退火算法, ftp://202.118.239.46/Incoming%2FeBook%2F%C4%A3%C4%E2%CD%CB%BB%F0%CB%E3%B7%A8.pdf,1994
[106]G.Karypis, V.Kumar.Multilevel k-way hypergraph partitioning.In: Proceedings of the Design and Automation Conference, 2009, 243~348
[107]W.M.Shaw, R.Burgin, P.Howell.Performance standards and evaluations in IR test collections: Cluster-based retrieval models. Information Processing and Management, 1997, 33(1):1~14
[108]C.Schmitz.Self-organization of a Small World by Topic.In: Proceedings of First International Workshop on Peer-to-Peer Knowledge Management, Boston, MA, August 2004.
[109]L.Guo, S.Jiang, L.Xiao et al.Exploiting Content Localities for Efficient Search in P2P Systems.In:Proceedings of 18th International Symposium on Distributed Computing (DISC 2004), Amsterdam, Netherlands, LNCS, 2007, 3274:349~364
[110]T.Bonald, A.Proutiere,J.W Roberts,Statistical Performance Guarantees for Streaming Flows Using Expedited Forwarding,Proc.IEEE INFOCOM,2001,1104~1112
[111]T.Bonald, J Roberts,Congestion at Flow Level and The Impact of User Behavior,Comput.Netw,2003,42:521~536
[112]B Suter,T V Lakshman,D stiliadis,Buffer Management Schemes for Supporting TCP in Gigabit Routers with Per-flow Queueing,IEEE J.Select.Areas Commun,1999,17:1159~1170
[113]U Black, IP Routing Protocols: RIP, OSPF, BGP, PNNI and Cisco Routing Protocols, http://portal.acm.org/citation.cfm?id=331258, 2009
[114]J Pu, E Manning, GC Shoja, A Srinivasan, A New Algorithm to Compute Alternate Paths in Reliable OSPF (ROSPF),Internet Conference on Computer,2001
[115]M.Jovanovic, F.S.Annexstein, K.A.Berman.Modeling peer-to-peer network topologies through small-world models and power laws.IX Telecommunications Forum TELFOR, 2009, 20~22
[116]D Comer, Internetworking with TCP/IP: principles, protocols, and architecture, http://www.google.com/books?hl=zh-CN&lr=&id=jonyuTASbWAC&oi=fnd&pg=PR23&dq=RIP+OSPf&ots=i3ZhR6ZPZq&sig=Z6RJ4g7ri71Gery-wbfM_SS90WA, 2006
[117]M.Faloutsos, P.Faloutsos, C.Faloutsos.On power-law relationships of the Internet topology.In:Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication,1999, 251~262
[118]JM Kleinberg, Navigation in a small world, Nature, 2000
[119]S.Bordag,G.Heyer,U. Quasthoff.Small worlds of concepts and other principles of semantic search.In:Proceedings of Innovative Internet Computing Systems Second International Workshop (IICS),LNCS,2003,2877:10~19
[120]Z.Xu, R.Min, Y.Hu.Reducing maintenance overhead in DHT based peer-to-peer algorithms.In: Proceedings of Third International Conference on Peer-to-Peer Computing, 2003, 218~219
[121]B Awerbuch, A Bar-Noy, M Gopal, Approximate Distributed Bellman-ford Algorithms, IEEE Transactions on Communications,1994
[122]A.B.Teslyuk, S.A.Krashakov, L.N.Shchur.On the universality of rank distributions of website popularity.Computer Networks, 2006,50(11): 1769~1780
[123]Oskar Sandberg.Searching in a Small World.[Doctor Dissertation], Goteborg University,Goteborg, Sweden, 2008,14~15
[124]P Echenique,J Gomez-Gardenes,Y Moreno, Improved Routing Strategies for Internet Traffic Delivery, Physical Review E,2004
[125]P Echenique,J Gomez-Gardenes,Y Moreno, Dynamics of Jamming Transitions in Complex Networks, Europhysics Letters,2005,71:325
[126]P Echenique,J Gomez-Gardenes,Y Moreno, Distance-d Covering Problems in Scale-free Networks with Degree Correlations,2004,70:056105
[127]Y Moreno,R Pastor-Satorras,A Vazquez, Epidemic Outbreaks in Complex Heterogeneous Networks, The European Physical Letters,2006
[128]L.A.Adamic, R.M.Lukose, A.R.Puniyani et al.Search in power-law networks.Physical Review, 2009, E64:046135
[129]B Brand, Method to Route A Network Nnitiated Message in A Complex Network Using Radius Protocol,http://www.freepatentsonline.com/EP1909450.html, 2008
[130]Ulric, A Fast Algorithm for Betweenness Centrality , Journal of Mathematical Sociology,2005