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

1、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

2、J. The structure and function of complex networks J. SIAM Review, 2003, 45(2): 167-256.,复杂网络理论的主要研究方法,引用图论中的已有的概念，并根据实际应用定义新概念，度量网络拓扑的结构特征。 节点度、节点间最短路径、网络直径； 节点度分布、网络平均路径长度，节点聚集系数、网络聚集系数 、节点度关联性、图谱。 根据前述定义，通过网络测量和统计分析的方法，分析网络的拓扑结构特征。 小世界特征、节点度的幂率分布、节点度的同/异配性、社团结构。 根据发现的网络特征，建立网络模型，利用蒙特-卡罗方法或非线性理论分析优

3、化网络性能。 搜索、病毒传播、容错性。,聚集系数的定义,聚集系数描述了节点和网络的聚集程度1： 节点聚集系数 网络聚集系数,例 C1=1/3C2=1 C3=0C4=0 C5=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)中随机选择一个节点vi，则该节点的聚集系数Ci是一个随机变量，称为节点聚集系数随机变量。 节点聚集系数随机变量Ci取值于0,1

4、区间的有理数。 例： 0，1/2，1； 0，1/3，2/3，1； 0，1/6， 2/6，3/6，4/6，5/6，1； 节点聚集系数随机变量Ci是非连续的、离散的，但是其包含无穷个离散值，并且离散值之间的间隔是非均匀的，因此传统的分布函数定义不适合该随机变量。,节点聚集系数的分布函数,定义 一个包含N个节点的网络G(V, E)，其节点聚集系数的分布函数P(C) 表示一个随机选定的节点v的聚集系数恰好位于C附近区间的概率。实际网络的计算如下面公式，其中|表示集合的尺寸，V(C)为聚集系数位于C附近区间的节点集，m为自然数，C取离散值：1/2m, 3/2m, ,(1-1/2m)。,Gnutella

5、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，还包含高聚集度节点。,1 Albert R, J

6、eong 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的邻居节点

7、集合。,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): 1

8、67-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-club1，那么Gnutella网络的聚集度同配性是否也会形成类似的结构？ 分别由Gnutella网络中聚集度最高的2和1%比例节点集导出两个子图。经过计算，这两个子图分别包含186和553个互不连通的部分，平均每个部分包含的节点数分别为1.7和2.8。两个导出子图的连通性非常差，说明该网络中的高聚集度节点并未形成rich-club。,1 Zhou S, Mondragon RJ. Accurately modeling the Internet topolo