网络中节点聚集系数的分布特征研究

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,P2P,网络中节点聚集系数的分布特征研究,-,基于复杂网络理论的,Gnutella,网络拓扑分析,清华大学 电子工程系 张珂,2007-11-6,提纲,复杂网络理论介绍,网络的节点聚集系数分布特征,节点聚集系数随机变量及其分布函数定义,Gnutella,top-level,拓扑的相关分析,网络的节点聚集度关联性,节点的聚集度,-,聚集度分布定义,Gnutella,top-level,拓扑的相关分析,总结,网络的图表示,一个具体网络可抽象为一个由节点集,V,和边集,E,组成的图,G(V,E),1,。,例如：,Internet-AS,、,Internet-Router,、,WWW,、,P2P,、电子邮件。,1 Newman M E J. The structure and function of complex networks J. SIAM Review, 2003, 45(2): 167-256.,复杂网络理论的主要研究方法,引用,图论,中的已有的概念，并根据实际应用定义新概念，度量网络拓扑的结构特征。,节点度、节点间最短路径、网络直径；,节点度分布、网络平均路径长度，节点聚集系数、网络聚集系数 、节点度关联性、图谱。,根据前述定义，通过网络测量和统计分析的方法，分析网络的拓扑结构特征。,小世界特征、节点度的幂率分布、节点度的同,/,异配性、社团结构。,根据发现的网络特征，建立网络模型，利用蒙特,-,卡罗方法或非线性理论分析优化网络性能。,搜索、病毒传播、容错性。,聚集系数的定义,聚集系数描述了节点和网络的聚集程度,1,：,节点聚集系数,网络聚集系数,例,C,1,=1/3C,2,=1,C,3,=0C,4,=0,C,5,=1/3,C=1/3,1 Watts, D. J. and Strogatz, S. H., Collective dynamics of small-world networks, Nature 393, 440442 (1998).,3,2,1,4,5,节点聚集系数随机变量,从一个网络,G(V,E),中随机选择一个节点,v,i,，则该节点的聚集系数,C,i,是一个随机变量，称为节点聚集系数随机变量。,节点聚集系数随机变量,C,i,取值于,0,1,区间的有理数。,例：,0,，,1/2,，,1,；,0,，,1/3,，,2/3,，,1,；,0,，,1/6,，,2/6,，,3/6,，,4/6,，,5/6,，,1,；,节点聚集系数随机变量,C,i,是非连续的、离散的，但是其包含无穷个离散值，并且离散值之间的间隔是非均匀的，因此传统的分布函数定义不适合该随机变量。,节点聚集系数的分布函数,定义,一个包含,N,个节点的网络,G,(,V,E,),，其节点聚集系数的分布函数,P,(,C,),表示一个随机选定的节点,v,的聚集系数恰好位于,C,附近区间的概率。实际网络的计算如下面公式，其中,|,表示集合的尺寸，,V(,C,),为聚集系数位于,C,附近区间的节点集，,m,为自然数，,C,取离散值：,1/2,m, 3/2,m, ,(1-1/2,m,),。,Gnutella top-level 拓扑分析,节点聚集系数分布,满足幂率分布，网络中存在相当数量的高聚集度节点。,数据来源：Stutzbach D, Rejaie R. Capturing Accurate Snapshots of the Gnutella NetworkC / Proceedings - IEEE INFOCOM 2005. NJ: IEEE, 2005, 2825-2830.,Gnutella,网络中节点聚集系数分布与网络连通性,删除高聚集度节点后的网络分裂的子网络数,该表说明，,Gnutella,网络的安全弱点不仅包含传统认为的高节点度节点,1,，还包含高聚集度节点。,删除节点比例,删除节点的聚集系数下界,子网络数,2,0.675,20,5,0.375,83,10,0.236,200,1 Albert R, Jeong H, Barabasi A L. Attack and error tolerance of complex networksJ, Nature, 2000, 406: 378-382.,节点的聚集度关联性,目前关于网络节点关联性的研究主要集中于节点度,1,2,，相关测量及度,-,度分布研究发现社会网络是节点度同配的，而信息网络是异配的,3,。,为了研究网络节点关于聚集度的关联性，定义聚集度,-,聚集度分布。,定义：节点的聚集度,-,聚集度分布表示节点邻居的聚集系数均值与该节点的聚集系数之间的关系。实际网络的计算如下面公式所示，其中,C,、,V,(,C,),与聚集度系数分布定义中意义相同，,N,(,w,),表示节点,w,的邻居节点集合。,1 Pastor-Satorras R, Vazquez A, Vespignani A. Dynamical and correlation properties of the InternetJ. Physical Review Letters, 2001, 87: 258701.,2 张国强, 张国清. Internet网络的关联性研究J. 软件学报, 2006, 17(3): 490-497.,3 Newman M E J. The structure and function of complex networks J. SIAM Review, 2003, 45(2): 167-256.,Gnutella top-level 网络的聚集度关联性,节点的聚集度,-,聚集度分布,该分布大致是一个递增的函数，因此,Gnutella,网络具有聚集度同配性。,数据来源：Stutzbach D, Rejaie R. Capturing Accurate Snapshots of the Gnutella NetworkC / Proceedings - IEEE INFOCOM 2005. NJ: IEEE, 2005, 2825-2830.,Gnutella网络中聚集度同配性与rich-club,研究表明复杂网络的节点度同配性会形成所谓的,rich-club,1,，那么,Gnutella,网络的聚集度同配性是否也会形成类似的结构？,分别由,Gnutella,网络中聚集度最高的,2,和,1%,比例节点集导出两个子图。经过计算，这两个子图分别包含,186,和,553,个互不连通的部分，平均每个部分包含的节点数分别为,1.7,和,2.8,。两个导出子图的连通性非常差，说明该网络中的高聚集度节点并未形成,rich-club,。,1 Zhou S, Mondragon RJ. Accurately modeling the Internet topology. Physical Review E, 2004, 70:066108.,总结,Gnutella,top-level,网络拓扑具有如下两个特征：,节点聚集系数的幂率分布,节点的聚集度同配性,下一步工作：,研究上述特征的产生机制,研究上述特征对网络性能的影响。,Q&A,