小世界进化模型研究(共享).doc

小世界进化模型研究关键词：小世界网络，DSW网络，P-SW网络，对数正态分布摘要网络分析是种有效的分析金融市场及社会问题的工具在本文中，我们基于苦名的 Watts-Strogatz的小世界网络，采用了理论分析和计算机模拟的方法，通过引入节点连接数正 态分布的方法提出两种网络模型一一DSW网络和P-SW网络并且我们在理论与计算机模 拟两方面得到了相符合的结论改进后的网络可以更好地适应现实问题特别在经济及其他成 员具有不同重要性的社会领域另外，我们通过调节网络适当的参数得到了其他有趣的结论 我们期待这些改进的网络能在今后的不同种金融市场及其它社会领域分析中起到作用1引言网络分析是种强大的分析金融市场和社会问题的手段［l-12］o至今，我们发现两种基本 的实际复杂网络的属性：small world（小世界）性质（类似于社会体系中著名的六度分割现彖， 通过极少数步骤从一个指定节点到达另一个节点）和scale-free性质（每个节点连接数的概率 满足幕律分布，即scale-free［3］）o著名的 Watts-Strogatz （W-S）小世界网络是 Watts和 Strogatz［l,13］提出的。

该模型由一个规则的环组成，通常是一个一维的几乎具有周期性边界 条件的环（即环中每个节点几乎都连接到一固定数冃的邻近节点）和少量的随机选取节点连 接成的“捷径”（重新连接现存的边）小世界网络同时具有“高网络聚集度”和“低平均路 径”的特性［2］聚集意味着如果个体有共同的朋友，则两个个体更有可能成为朋友而“低 平均路径”意味着平均路径随着节点数增长仇仅以指数形式增长这显示了任意两个人可以 通过比较短的中间连接取得联系在本文中，我们定义“或厂）为平均路径，C或（CJ代表 聚集度，斤代表每个节点在重新连接（加入捷径）前连接到邻近点的点的数目在小世界网络中，已被证明我们可以加入少量的捷径来大幅度降低/然而C几乎保持不 变［1］如果我们可以找到一些实际生活中的模型符合小世界的特性，我们根据这个/和C 的特性可以得到一些重要的特性例如，一些研究者发现因特网［3］和疾病传播⑶具有小世 界特性，因此我们nJ以通过在一些不相干网站上加入链接的方法来增加因特网的安全性以及 通过减少不相干人群接触的方法减少疾病传播范围然而，我们有一些计算/［2］和口3］的方法在通过大量对那些具有小世界特性的实际情 况与理想小世界模型的比较^［4-8］,可以发现⑶一些路径和聚集度的偏差。

关于这个问题, 可能的原因是，在小世界模型中，在重新连接前要求每个节点连接到固定数H的邻近节点以 及真个网络具有一个相同的概率来加入捷径因此，该模型可能无法非常好地符合现实惜况在本文中，我们提出2个进化的小世界模型来克服这两个问题对于笫一个问题，我 们构造一个标准的小世界网络但每个节点实际上是独立的小世界网络而对于每一个这些所 谓的“节点”只包括所有的那些在重新连接前具有相同连接数的“小节点”（在不同“大节 点”中的“小节点”具冇不同数II的到邻近节点的连接数）在图2中每个大节点都是个小 世界网路因此在此模型中，我们可以给定一个&的范围并构造一个大的小世界网络我们 根据对数正态分布决定了每个&的节点数的比例［14］为了方便起见，我们让所有网络重新 连接边的概率相同Z后，基于参考文献［2・3］中的理论，我们提出一些方法来计算/和6 另外，我们也进行一些计算机模拟非常有趣的是，计算机模拟与理论俏収得了比较相近的 结果，这表明了我们预期理论的冇效性Z后，我们比较了真实情况与我们新的模型的数据 并最终分析一些我们新模型的侑趣的特性这个模型可能更好的适用于阶级现象由于它使得 节点有不同的重要性，所以该模型被期待拥有大量社会问题的应用，我们可以使用该新模型 的特性来更精确地分析社会现彖。

因为这种节点的双重性，我们可以称这种模型为“双小世 界模型（DSW）”对于第二个问题，我们构造一个类似于W・S小世界网络的模型但使用不同 的构造方法它类似于W-S网络模型的构造但具冇不同方法来添加捷径模型中每个节点 有口己的概率•其他非邻近于该节点的节点联系每个概率值的节点个数的比例也由对数正 态分布决定为了方便起见，我们在后血叫这个模空“P・SW”结果显示了这两种模型都能 更满意地适应真实情况而这两种模型也具有类似W-S模型的特性因此，我们可以用更精 确模型来分析不同种类的实际悄况，并有可能有更好的解决方案解决问题，尤其是经济学和 其他成员不具有平等重要性的社会领域因此一些真实情况如疾病或信息传播可能可以根据 我们新的模型来让人更信服、有效地进行分析2 W・S模型的缺点一个W・s模型是一个介于在下面定义的规则网络与随机网络间的网路我们从一个具 有77个节点的环开始，每个节点连接到&个邻近节点我们可以考虑每条边并给一个P作为 重新连接该条边（叫做捷径）的概率为0则我们称该网络为规则网络，如果为1 我们称Z为随机网络在此，我们可以认为小世界网络是当P介于o和I之间是的网络在 小世界网络的定义之后，我们开始给出确切的/和C的定义。

我们定义“刃为所有点到点路 径的平均路径长度，C（刃为聚合系数假设一节点卩冇人条边，即人个节点连接到V在 这仏个节点中最大连接数目为人％・1）/2如果我们定义G，为实际连接边数出一•最大数目的 比值,那么C（刃即为平均的C对于W-S小世界网络模型，我们有两个关于/［2］和［3］的公式' =original V5 /tanh-1C(k) =3k(k-l)2R(2k—1) + 8 冰 2+4”2r2(2)(1)其中(3)歹=npk / 2.一些实际情况己被证明具有-•些小世界特性［6-9］, W以我们可以比较这些有小世界特性 的模型和理论W-S模型使结论更具说服力我们用实际/数据与关于/的公式（公式1）来算出相关的P然后我们用新得到的P 来计算C因此我们可以通过W-S模型得到一个理论值C和根据实际数据得到的真实值C （真实值O是实际情况的真实聚合度）表1显示了虽然这些模型具有小世界网络的特征，他们并不非常好地满足W-S小世界 网络（因为聚合度并没有符合）丿&管这些模型被认为相似于小界网络，偏爰还是依然存 在的这种偏差可能是由于在重新连接前的固定连接数和每条边重新连接的相同概率（构造 捷径）造成的。

模型NC(w-s)C(actual)C(random)LANL co-authorship[4,5]529090.580.430.00018MATH[6]709750.480.590.000054Neurosi[6]2092930.600.760.000055E.coli,substrate graph[7]2820.540.320.026Words[8]4609020.690.440.0001C.Elegans[l]2820.620.280.005表1： W-S模型和实际情况的比较这里n代表节点数,C代表聚介系数,C（W-S）代表通过 理论公式得到的结果（方程2）, C（acmal）代表从数据中得到的实际结果通过实际模型的聚 合系数和相关随机网络的聚合系数的比较,这些模型被认为有小世界特性 13］3两种网络的描述因为一个W-S模型是源口于每个节点具有固定连接边数的规则网络，该模型可能不能非常 好地适和实际情况因此，有必要改进w・s小世界网络3.1 DSW模型现在我们开始构造DSW模型首先构造一个标准的小世界网络（图1）,但每个（“大”） 节点事实上由一个次小世界网络组成（图2）每个“大”节点包括所有的拥有在重新连接 前连接边数相等的事实上的“小”节点。

须注意的是不同“大”节点中的“小”节点拥有不 同的重新连接前的连接数因此在这个网络中，我们可以给R—个范围然后使所有“人”节 点成为一个网络在这里，我们用对数正态分布来决定每个k值的节点数得比例（如［14］ ）o 现已发现很多体系存在这种分布，如金融市场［15］,铁磁流体实验［16］等等［17］与原始W・S 模型一样，我们在新模型中保持所有边重新连接的概率一致DSW模型可能更适应社会中 阶级分层的现象因为该模型每个节点具有了不同的重要性，因此该模型在社会问题中可能有 更大的潜力在社会生活中阶级分层现彖是非常常见的，因此我们可以在重新连接前把具有 相同连接数的节点聚集在一起在这里，我们也需要重新连接一些边并构造一些捷径，见图 2o然后我们把这些大节点较弱地连接起來使其满足实际的阶级分层情况，他们也向小世界 网络一样连接，也具有捷径当一个大节点连接到另一个大节点，这意味着一个大节点中的 一个小节点与另一个大节点中的一个小节点相连（小节点被随机选择，见图1和图2）为了使大节点间的连接比较弱，我们令大节点中节点到另外节点的连接数（R）为2 在自然界中，己被证实许多事物满足对数正态分布这里我们也运用该定律（方程5）来计 算每个&值的节点数的比例。

在对数正态分布图］:网络的大节点（k=2并fl网络中存在1条捷径）中，§表示中间参数，表示该参数的标准偏差另为，为了方便起见，最小值被设为2 在实际情况中标准偏差o和中间参数§可以改变在我们得到DSW模型Z后，我么试图求出关于新模型厂和L的公式首先为了方便, 我们设对数正态分布的参数为M2因此，我们得到—^original (nf(i)pkf),Jt中k'=k/2o对数正态分布的表达式为 在这里分布函数必须满足maxXao-i./=1我们把该模型分解为矶X个组（人节点）然后我们设最小值L等于 1 ,最大值疋等于Max之后我们可以求出DSW模型相关的/和C, 我们定义为/'和C'图2：网络中实际的节点（大节点是在重新连接前每个节点连接数（k）相同的节点的 集合） 对于/;我们考虑两个部分一部分是大节点内部的部分另一部分是大节点与大节点间 的外部部分我们首先计算两部分的总长度然后再除以总路径数我 们得到max 1L 爲® = ⑴ 一 1］心,刃“⑴,r=i 'maxouter =心妙［恥刃(l,p) +》［/(l,p财⑴］/加处［加处+ /(l,p) + l］］, ⑻1=1心疋严⑷一1）/2 —工”⑴时⑴―1]/2, （9）i=l心（厶爲「+厶爲）心⑺一1）/2]・ （10）在得到/'后我们开始考虑CS因为大节点间的联系非常弱而&事 实上是最小值，我们可以忽略大节点与大节点间连接的影响因为不同 大节点间小节点的联系非常少。

因此我们只需计算每个节点的内部 因而我们得到C =工[C⑵）叭伽 （11）/=/对于此模型，我们令正态分布的平均连接6为0. 5kg吋另一方 面，我们通过计算模拟作比较（图3 ）图3和图4说明改进的理论在 计算机模拟中非常匹配，证明了公式1 0和公式1 1的正确性3.2关于P-SW模型在这里我们运用种新的方法來构造捷径每个节点有日己的概率”这里概率对比与 在W・S中的概率具有了不同的含义我们制定一个节点，然后考虑每个不连接于该节点的 节点该概率是判断是否应该在选定界定与每个不于该节点连接节点间填一条边为了更好 地适应实际情况，我们也给每个概率值得节点数的比例对数正态分布之后，我们选取了不 同参数用计算机程序模拟来研究这种网络m- thecry -—sJnxiattcrF-1C3D rnac*=0 30 an QM0 06 sot «w， deccy ----5 m ji 30 orr-1XO o<12Sr。