埃及信息学杂志（2021）22，389开罗大学埃及信息学杂志www.elsevier.com/locate/eijwww.sciencedirect.com全长文章一种基于两跳邻居偏好的随机一种用于复杂网络Natarajan Meghanathan*，Aniekan Essien，Raven Lawrence杰克逊州立大学，杰克逊，MS 39217，美国接收日期：2015年11月15日;修订日期：2016年4月22日;接受日期：2016年6月19日2016年9月8日Erdos-Renyi（ER）随机网络模型是在假设两个节点u和v之间可能存在一个链接u-v的情况下生成图的，而不管节点u和v之间是否存在链接u-v。两个节点在链路建立之前具有共同的邻居。结果，在ER模型下生成的随机网络图的特征在于具有低聚类系数（节点的任何两个邻居之间存在链路的概率的度量）和节点度的低变化，并且因此不能与抽象真实世界网络的图紧密匹配。在本文中，我们提出了一个随机网络图模型，该模型优先封闭包含三个节点u，w和v的三角形，其中存在链接u-w和w-v（即，节点V严格地是节点U的两跳邻居）。因此，当节点u正在寻找与其他节点x建立的新链路时，我们将x与u的两跳邻居一起考虑，并在这些节点中选择概率为p的节点作为节点u的新邻居。提出的基于两跳邻居偏好（THNP）的模型生成的随机图的聚类系数随着节点度的增加而减小：与通常用于复杂网络分析的几个真实网络图紧密匹配。©2021 THE COUNTORS.由Elsevier BV代表计算机和人工智能学院出版开罗大学情报处。这是一篇CC BY-NC-ND许可证下的开放获取文章（http：//creativecommons.org/licenses/by-nc-nd/4.0/).1. 介绍随着社交网络的增长和关于几个真实世界网络（例如生物网络）的数据的可用性*通讯作者。电子邮件地址：natarajan. jsums.edu（N. Meghanathan）。开罗大学计算机和信息系负责同行审查。和引文网络），从图论的观点分析这些复杂网络已经引起了极大的兴趣分析复杂现实网络的关键步骤是提取网络中顶点的度分布泊松、高斯、指数、幂律等）网络[1]使用与真实世界网络相同的参数（例如平均节点度和节点度的标准差）从理论模型中生成一旦http://dx.doi.org/10.1016/j.eij.2016.06.0081110-8665© 2021 THE COURORS.由Elsevier BV代表开罗大学计算机和人工智能学院出版。这是一个在CC BY-NC-ND许可证下的开放获取文章（http：//creativecommons.org/licenses/by-nc-nd/4.0/）。关键词两跳邻居;随机网络图;Erdos-Renyi模型;复杂网络分析;聚类系数390N. Meghanathan等人识别了用于现实世界网络的等效理论图模型，可以基于所识别的图模型的参数和分析度量来有效地分析现实世界网络的各种对某些现实网络的分析结果表明，这些网络中顶点的度分布与任何已知的分布都不匹配。例如，我们观察到（从图1中）本文研究的一些真实世界网络样本的度分布是泊松曲线（随机网络的特征）[2]，但具有长尾（无标度网络的特征），有时甚至具有长头。如果将这些真实世界的网络建模为随机网络，则无法捕获少数但数量可观的顶点的存在，这些顶点的度显著大于其余顶点。此外，随机网络不能捕捉顶点的聚类系数随着节点度的增加任何两个节点之间的链接的概率）[3]。对另一方面，如果这些真实世界的网络被建模为无标度网络[4]，那么人们会错误地捕捉到度较低的顶点的度分布;虽然无标度网络预计会有更多的度较低的顶点，但图1所示的真实世界网络只有较少的度较低的顶点。因此，图1中的观察结果的动机是，我们需要一个随机网络图模型，该模型可以捕获较小的，但是具有较低度数和较高度数的顶点的可观百分比（即，节点度的较大变化）。在同时，我们也希望该模型能够捕捉到聚类系数与节点度之间复杂的反比关系。在本文中，我们提出，每当我们正在寻找一个链接建立一个节点u，我们优先考虑节点u的两跳邻居，而不是一个任意的节点，可能会或可能不会是一个两跳邻居的节点u之前建立的链接。我们假设所提出的方法可以导致几个两个链接链作为三角形闭合-与急诊室模型具有生成具有较低节点度变化（大多数顶点的度接近平均度）和较低聚类系数（ER随机图中任何顶点的聚类系数接近任何两个节点之间的链接的概率）的随机网络图的特性。根据所提出的两跳邻域优先（THNP）方法，如果我们要为节点u建立新的链路并决定该节点是否要与随机选择的候选节点x（节点u与该候选节点x还没有链路）配对，则我们考虑节点x以及节点u的两跳邻居（即，存在两跳链，比如涉及链路U-W和W-V的U-W-V），并且以概率（P 链 路）在节点中随机选择一个（从扩展的候选列表中）作为邻居节点。THNP模型中使用的p链接值与ER模型中使用的p链接值相同，并且通过将真实世界网络的平均节点度除以节点数-1来获得与基于ER模型的随机网络图不同，基于THNP模型的随机网络图表现出聚类系数与节点度的反比关系以及节点度的较大谱半径比（即，节点度的较大变化）[6]。我们通过计算平均节点度、平均聚类系数、平均路径长度和节点度的谱半径比的均方差的根和来评价根据THNP模型和ER模型生成的图与真实世界网络图的相对接近性（相似性）我们观察到的THNP模型为基础的随机网络图是相对更类似于现实世界的网络图考虑，相比ER模型为基础的随机网络图。本文的其余部分组织如下：第2节讨论了相关的理论模型的工作，产生网络的聚类系数值和分布类似于现实世界的网络观察。第三节提出了THNP模型，用于生成具有较大聚类系数和较高节点度变化的随机网络图第4节回顾了ER模型，介绍了本文中考虑的真实世界网络图，并说明了ER模型和THNP模型与真实世界网络图在上述分析度量方面第5节空手道俱乐部网络美国政治图书网C. Elegans神经网络(34节点，78条边）(105节点，441条边）(297节点，2148条边）图1度分布和聚类系数与真实世界的网络。具有高聚类系数的随机网络图模型391-总结了本文的研究成果。在整个论文中，我们可以互换地使用术语意思是一样的。2. 相关工作在本节中，我们介绍了文献中的相关工作，这些工作是关于提出来生成网络的理论模型，这些网络的聚类系数分布与真实世界网络的聚类系数分布相似，并且还强调了网络的独特特征。(s)我们提出的THNP模型与这些现有模型的区别。在[14]中，作者提出了一个无标度随机图的模型（网络大小随着一次添加一个节点而增加），其中每个新的顶点以与现有节点的度成比例的概率添加到m个现有节点上加上一个严格的正常数（后者与节点选择中的随机性有关）。结果表明，用上述方法生成的无标度随机网络的期望聚类系数与logn/n渐近成正比. THNP模型与上述模型不同，因为可用于为节点u建立链路的节点的候选列表是u的两跳邻居和最初考虑用于链路的随机选择的节点v。在两跳邻居中，具有较大数目的公共邻居的节点被给予相对较高的优先级。并非网络中的所有节点都被考虑用于为节点u建立新链路。这类似于当节点/用户希望建立新链接时在社交网络中发生的情况;用户更可能搜索他/她的朋友的朋友，而不是搜索网络中的某个随机用户。此外，如果我们将上述logn/n公式应用于本文中考虑的真实世界网络图，则预期的聚类系数变得非常小（例如332节点的美国机场网络为0.0076，34节点的空手道俱乐部网络为0.045），并且与节点度无关在[15]中，作者提出了一个生成随机交图的模型：设W是n个顶点的集合，设D1，D2，. . .是n个顶点的随机创建的子集;如果两个顶点u和v是n个顶点的至少s个子集中的至少一个子集中的至少两个顶点u和v被认为是图中链接的，其中sP1是模型参数。在[16]中观察到，随机相交图的聚类系数与节点度之间呈现线性反比关系（即，节点的聚类系数与k-1成比例，其中k是节点度）。在本文中，我们观察到聚类系数-度关系不需要是简单的线性关系，它可以更复杂，如图所示。 12（a）-（f）. 因此，随机交叉图模型不足以对聚类系数和节点度之间的复杂逆关系进行建模，如在几个真实世界的网络中所看到的。在[17]中，作者提出了一个生成度分布遵循幂律的随机图的模型[4]。其思想如下：（i）确定真实世界网络中顶点的度分布。(ii)通过生成每个顶点v的kv个副本来制作顶点列表，其中kv是顶点v的度数。（iii）通过对步骤（ii）中创建的顶点列表进行两次不同的随机洗牌来设置顶点列表的两列(iv)连接两列中每行上述方法的问题在于，对于具有多个顶点的真实网络，它可能导致具有自循环和冗余边的图。作者在[17]中提出了一些修正措施来克服这些弱点。然而，在这样的幂律随机网络中的顶点的聚类系数已被观察到是简单地依赖于幂律指数和节点的数量，但不是在节点的度。因此，上述用于生成基于幂律的随机网络的模型没有捕获聚类系数和节点度之间的反比关系，如在几个真实世界网络中观察到的，并且被所提出的THNP模型很好地捕获（参见第4节）。除了单独使用学位序列，还有一些积极的研究（例如，[18已经观察到这种方法产生可调的聚类系数。这个想法是输入三角度序列（即，每个节点是其一部分的三角形的数目）和单边度序列（即，入射到节点上而不是任何三角形的一部分的边的数量），以通过一次选择三个顶点并在它们之间创建三角形（如果它们的剩余三角度大于0）以及一次选择两个顶点并将它们连接（如果它们的剩余单边度大于0）来顶点的剩余三角形度和剩余单边度分别是顶点尚未成为其一部分的剩余三角形和单边数重复上述过程，直到顶点的残余三角度变为0并且顶点的残余单边度变为0。上述想法最早在[18]中提出，但没有澄清在迭代中选择哪三个顶点用于三角形形成，哪两个顶点用于单边形成。在[19]中，作者提出了几种策略（例如，基于三角度与三角度之和的比值、单边度与单边度之和的比值等）。用于选择三角形和单边形成的顶点。上述方法背后的一个关键弱点是，计算三角形的数量和每个节点所属的单边的数量需要大量的时间。此外，完成所有三角形形成的收敛时间将很长（因为任何三个选定的节点不需要有一个三角形连接它们）。另一方面，我们提出的THNP算法的优点是，它只需要在现实世界中的任何两个节点之间的链接（p链接）的概率的估计值网络作为输入（plink=hki/N-1，其中-hki=2*L/N是平均度，N和L是数分别为节点和链路的数目），并且可以基于真实世界网络图中的节点和链路的数目来简单地计算P链路值3. 两跳邻居偏好（THNP）模型假设总共有N个节点，我们需要在其中生成一个具有较大聚类系数和较高节点度变化的随机网络设plink是所考虑的任何节点对之间的链路的概率最初，所有节点都被认为是孤立的网络。我们考虑所有可能的节点对的集合S（N个节点的网络具有N（N1）/2个节点对）。网络生成在迭代中进行。在每次迭代中，我们从集合S中选取一个节点对u-x，然后运行-392N. Meghanathan等人-我们在两个顶点（u或x）中选择一个作为节点，我们试图在该迭代期间为该节点建立链接。为了便于讨论，我们假设（不失两个顶点u或x之间的一般性），顶点u被选为我们试图为其建立链接的顶点。设C是候选顶点的列表，我们可以用它来为u建立链接。我们将顶点x作为第一个顶点添加到列表C中。然后我们考虑u的所有两跳邻居v（即，通过链u-w-v连接，其中w是u的直接邻居），它们不直接连接到顶点u，并将它们添加到列表中C.我们从列表C中随机选取一个顶点（比如顶点v）。我们在[0.. . 1]。如果random =6plink，则在u和v之间建立一个链接;否则不建立。如果u和v之间建立了联系，我们从集合S中删除u-v对。不管迭代的结果如何，我们从集合S中删除u-x对，并继续下一次迭代。我们在每次迭代中重复上述步骤，直到集合S变为空。图2给出了THNP算法的伪代码。关于时间复杂度，第1-5行在H（N 2）时间内执行，其中N是网络中的节点数。第6-32行的while循环总共运行N次（N 1）/2=H（N2）次迭代-每个节点对一次迭代。对于每个这样的迭代，可以执行第7-17和25-31行行18-24涉及顶点的两跳邻域的遍历。如果K=2 L/N是具有总共L个链接的最终网络中节点[3]的平均度，则第18 - 24行的每次执行平均花费H（K 2）时间（因为基本上节点的K个邻居中的每个邻居的邻居被探索作为搜索两跳邻居的一部分）。因此，对于H（N 2）次迭代中的每一次，行18-24可以被认为具有复杂度H（L 2 / N 2）。因此，从第7-30行开始的while循环的每次迭代可以被认为花费H（L 2 / N 2）时间，并且对于总共H（N 2）次迭代，第6-32行的时间复杂度为H（L 2）。因此，在THNP模型下生成随机图的算法的总时间复杂度为H（N2）-（对于行1-5）+ H（L2）-（对于行6-32）= H（N2 + L2）.3.1. 与社交网络的随着新链路的添加，节点的两跳邻居的数量增加，并且节点u很有可能与其两跳邻居之一链接，而不是链接到不在其两跳邻居中的节点。在社交网络中，如果用户打算与网络中的某人配对，则用户更可能偏好与已知与该人配对的某人配对。输入：节点数，N;链路概率，p链路输出：链接集，E辅助变量：节点对集，S;候选顶点列表，C;候选顶点中文（简体）开始THNP算法1对于每个顶点u= 1到N，2对于每个顶点v=u+1到N，3S =S<${（u，v）}4端5端6while（S）7从S中随机选择一对（u，x8S =S- {（u，x）}9C10在[0.[1]11如果r，则12C =C{x}13候选顶点=u14其他15C =C{u}16候选顶点=x17end if18对于每个顶点w，邻居（候选顶点）做19对于每个顶点v∈Neighbor（w），20如果vNeighbor（Candidate Vertex），则21C =C{v}22end if23端24端25从列表C中随机选取一个顶点v26C =C-{v}27在范围[0.[1]28如果随机 p链接29E=E<${（候选顶点-v）}30S=S- {（候选顶点，v）}31end if32end While33回路E结束THNP算法图2基于两跳邻居偏好的随机网络生成模型的伪代码具有高聚类系数的随机网络图模型393他 / 她 的 邻 居 ， 而 不 是 与 一 个 陌 生 人 配 对 。 包 括Facebook在内的几个社交媒体网络已经被设计为建议朋友的朋友作为发送朋友请求的可能候选人。因此，两跳邻居偏好模型非常适用于对社交网络中基于友谊的交互进行请注意，如果候选顶点的更多邻居将特定顶点作为其两跳邻居，则该顶点有更大的机会成为候选顶点的邻居。这与Facebook等社交网络中的链接是如何形成的是相关联的。如果用户A得到来自两个用户B和C的好友请求，并且处于仅接受这些好友请求中的一个的情况，则用户A更可能接受来自具有相对较大数量的共同好友的用户的好友请求。3.2. 示例说明THNP模型的执行图 3给出了一个例子来说明执行THNP模型的迭代以建立链路。假设从集合S中移除一对（3，5），并考虑为候选顶点=3（在顶点3和5中随机选择）建立链接由于顶点3被选为候选顶点，所以另一个顶点（顶点5）被包括到可以与候选顶点配对的顶点的列表C中。我们现在寻找候选顶点（顶点3）的两跳邻居，并将它们包含到列表C中。注意，两跳邻居顶点可以多次被包括到列表C中，每个邻居一个条目。我们观察到顶点8在列表C中有两个条目，因为它是顶点4和7的邻居其他两跳邻居（顶点1和6）在列表C中仅具有一个条目，因为它们是候选顶点3的仅一个邻居我们从列表C={1，8，5，6，8}中随机选取一个顶点。正如在模拟中所观察到的，在列表C中有多个条目的顶点有相对较大的机会被选中（增加闭合三角形的数量，从而增加整个网络的平均聚类系数）：我们观察到顶点8被选为候选顶点3将与之建立链接的顶点。3.3. 对更常见的两跳邻居图4说明了对平均聚类系数和平均路径长度的影响，这与更常见的两跳邻居图3THNP模型迭代的执行示例。（顶点8）相对于随机两跳邻居（顶点6）的偏好。我们注意到，链路3-8的设置将两条链3-4-8和3-7-8闭合成三角形（有助于获得更大的平均聚类系数0.21），但可能会增加从顶点4、5和6到其余顶点的跳数（有助于获得略大的路径长度1.96）。另一方面，链路3 - 6的建立仅闭合一个链3-7-6（有助于0.10的较低平均聚类系数），但相对减少了大多数节点对之间的最短路径上的跳数（平均路径长度为1.89）。因此，我们注意到，优先考虑更常见的两跳邻居，甚至可以加倍的平均聚类系数在一个非常温和的增加（增加不到5%）的平均路径长度的代价4. 模拟在本节中，我们将讨论基于所提出的THNP模型对现实世界的网络进行建模时观察到的仿真结果，并与著名的随机网络Erdos-Renyi（ER）模型进行比较。通常的做法是，如果在现实世界的网络或从模型（如THNP模型）生成的理论网络中观察到的某个属性（如较小的路径长度）与从ER模型生成的随机网络中观察到的属性一致，则该属性被认为是在现实世界的网络或理论网络中偶然观察到的[21，22]。另一方面，如果在现实世界或理论网络中观察到的某个属性（如聚类系数和节点度之间的反比关系）与在ER随机网络中观察到的属性不一致，则它确认存在一种潜在的机制（如THNP模型的两跳邻居偏好），可以归因于这种属性的观察[21，22]。因此，ER模型在文献中经常被用作理论基准模型，用于将观察到的特定性质归因于随机连接形成或优先连接形成。本节中的模拟结果表明（与ER模型不同）THNP模型在聚类系数和节点度之间呈现出反比关系（归因于链路形成的潜在两跳邻居偏好机制），这在几个现实网络中也可以观察到我们评估的接近度（相似性）的理论图生成的THNP和ER模型与抽象的现实世界的网络使用分析指标，如（i）平均聚类系数-CC的图形;（ii）平均路径长度-PL;（iii）平均度-K和（iv）光谱半径比节点度-SRK。第4.2节给出了计算上述每个分析度量的定义（包括定量公式）和程序。接近度值被建模为相对于理论图（缩写为ThG-可以指THNP或ER模型图）和现实世界网络图（在等式中缩写为RwG）的① ①）。根据该公式，目标（期望的）接近度值为0-的符号394N. Meghanathan等人ThGRwGCC卢旺达þThGRwGPL卢旺达þThGRwGKRwGþThGRwGSRK卢旺达偏好更常见的两跳邻居对随机两跳邻居的图4THNP模型-公式中的CCThG、PLThG、KThG和SPRThG（1）分别给出了由THNP模型或ER模型等理论模型生成的网络的平均聚类系数、平均路径长度、平均度和节点度的谱半径比的值同样地，在等式（1）中的符号CCRwG、PLRwG、KRwG和SPRRwG 也是相同的。（1）分别给出了实际网络图的平均聚类系数、平均路径长度、平均度和节点度的谱半径比的值4.2.1. 聚类系数节点的聚类系数是节点的任何两个邻居连接的概率[3]。量化地，节点的聚类系数被计算为连接节点的邻居的链路的实际数目除以节点的邻居之间的可能链路的最大数目的比率对于度为K的节点（即，K个邻居），则节点的邻居之间的可能链路的最大数目是K（K-1）/2。聚类系数-S.ffiffiffi ffiCffiffi ffiCffiffiffiffiffiffiffiffiffiffi ffi—ffiffiffiffi ffiCffiffi ffiCffiffiffiffiffiffiffiffiffiffi ffiΣffiffi ffi2ffiffiffiffiffiffiffi ffi.ffiffi ffiPffiffi ffiLffiffiffiffiffiffiffiffiffiffi ffi—ffiffiffiffi ffiPffi ffiffiLffiffiffiffiffiffiffiffiffi ffiΣffiffi ffi2ffiffiffiffiffiffiffi ffi.ffi ffi ffi ffiKffiffiffiffiffiffiffiffiffi ffi—ffiffiffiffi ffiKffiffiffiffiffiffiffiffiffi ffiΣffiffiffi ffi2ffiffiffiffiffiffi ffi.ffiffiffiffiSffiffiffiRffiffiffiKffiffiffiffiffiffiffiffiffiffiffi-ffiffiffiffiffiSffiffiffiRffiffiffiKffiffi ffiffiffiffiffiffiffiffiΣffiffiffiffi2ffi4.1. Erdos-Renyi（ER）模型我们模拟了ER模型下随机图的生成，输入参数为节点数N和任意两个节点之间的链接概率plink。我们累积所有可能的节点对的集合S我们在迭代中前进。在每次迭代中，我们从集合S中随机移除一对（u，v），并在范围[0. . 1]。如果random为6p，则设置链接u-v;否则不设置.用于在ER模型下生成随机图的上述过程的伪代码（图5所示）可以从图2中描述的伪代码改编。在ER模型下生成N个节点和L个链接的随机图的算法的总时间复杂度是H（N2），因为它是从第1-5行运行for循环的时间复杂度加上从第6-13行运行while循环的时间复杂度，这两者都可以在H（N 2）时间内完成。4.2. 分析指标在本小节中，我们简要介绍分析中使用的指标。网络的聚类系数（用于公式（1））是节点的聚类系数的平均值。 平均度为K = 2L/N的节点的聚类系数可以在H（K2）= H（L2/N2）时间内计算，因为这需要探索该节点的K个邻居中的每个邻居的邻域。计算网络的聚类系数的时间复杂度为H（NK2）=H（L2/N）。4.2.2. 路径长度两个节点u和v之间的路径的长度是u和v之间的最短路径上的最小跳数。平均路径长度（在公式（1）中使用）是平均值网络中所有节点对的路径长度。所有节点对的路径长度可以以距离矩阵的形式表示，并且可以通过在N个顶点的图上运行时间复杂度为H（N 3）的Floyd4.2.3. 程度节点的度（即，节点的邻居的数量）是在节点上入射的链路的数量网络的平均度（用于公式（1））是网络中所有节点的度值的平均值节点的度接近值¼ð1Þ具有高聚类系数的随机网络图模型395输入：节点数，N;链路概率，p链路输出：链接集，E辅助变量：节点对集，S中文（简体）开始ER算法1对于每个顶点u= 1到N，2对于每个顶点v=u+1到N，3S =S<${（u，v）}4端5端6while（S）7从S中随机选择一对（u，v）8S =S- {（u，v）}9在范围[0.[1]10如果随机p链接11E =E{（u-v）}12end if13end While14回路E结束ER算法图5Erdos-Renyi（ER）随机网络生成模型的伪代码。可以在H（K）=H（L/N）时间内计算，并且N个节点的网络的平均度可以在H（NK）=H（L）时间内计算。4.2.4. 节点度节点度的谱半径比[23]是主特征值（a.k.a.网络图的邻接矩阵[7]图的谱半径（记为ksp（G））使用时间复杂度为H（N3）的幂迭代方法[7]计算，最多涉及N次迭代;在每次迭代中，我们根据图的邻接矩阵（A）计算图的主在第（i+1）次迭代期间的主特征向量Xi +1由下式给出：||其中，X i是第i次迭代结束时图的主特征向量，||的axl||是A和Xi乘积的归一化值 。|| is the normal- ized value of the productof A and X i.首先，X i=[1，1，.. . ，1]-对应于图中的顶点数目的所有1的列向量。幂迭代法（如图所示）。 6）当标准化值||的axl||收敛，并且收敛的归一化值是谱半径。若Kmin、Kavg和Kmax分别为节点度的最小值、平均值和最大值，则Kmin6Kavg6ksp（G）6Kmax[8]成立.因此，节点度的谱半径比（SRK）（计算为ksp（G）/Kavg）将总是大于或等于1.0。4.3. 真实世界网络数据集在本节中，我们介绍了本文研究的六个真实世界网络数据集[9我们认为这六个网络是现实世界网络的代表，其节点度的谱半径比的值范围更广（即，以在节点度的变化中表示具有更宽范围的值的真实世界网络）。真实世界的网络被列出（按照节点度的谱半径比的递增顺序）如下（用于图6示出执行幂迭代方法以计算网络图的邻接矩阵的谱半径的示例396N. Meghanathan等人嗨嗨指的是在括号中表示的网络，紧跟在网络名称之后）：(i) 美国足球网络（FN）：这是一个由115支球队（代表I-A组大学）组成的网络，他们参加了2000年秋季美国足球赛季。节点代表球队，如果相应的球队在赛季中相互比赛，则两个节点之间存在边[9]。(ii) 美国政治图书网络（PN）：这是一个由105本与美国政治有关的图书组成的网络，在亚马逊网站上出售。每本书代表一个节点，如果有人买了对应于节点u的书，也买了对应于节点v的书，那么两个节点u和v之间就有一条边，反之亦然。(iii) 空 手 道 俱 乐 部 网 络 （ Karate Club Network ，KN）：这是20世纪70年代美国一所大学空手道俱乐部的34名成员的社交网络成员代表节点，如果对应的成员是朋友，则两个节点之间存在边[9]。(iv) C. Elegans神经网络（EN）：这是一个由两性小杆线虫中的297个神经元组成的网络[9]。每个神经元都是一个节点，如果相应的神经元相互作用（以化学突触，间隙连接和神经肌肉接头的形式），则两个节点(v) 悲惨世界网络（LN）：这是一个由维克多·雨果的小说《悲惨世界》中的77个角色组成的共现网络。每个字符代表一个节点，如果两个字符在书中至少一章中共同出现，则两个字符之间存在边[9]。(vi) 美国机场网络（AN）：这是一个1997年美国332个机场的网络。每个节点是一个机场，如果两个相应的机场之间有直飞航班，则两个节点之间存在边[10]。在图7中，我们使用Gephi[11]可视化和分析工具描述了六个真实世界的网络。使用的布局算法是顶点的颜色（从白到黑：灰度）是顶点聚类系数的度量-顶点的颜色越深/越黑，其聚类系数越大，反之亦然。顶点的大小是顶点度的度量-顶点的大小越大，其度越大，反之亦然。对于除美国足球网络（FN）之外的所有网络，我们观察到较大尺寸的节点（即，具有较大度数的节点）的颜色是苍白的（白色或接近白色）;而，较小尺寸的节点具有较小度数的节点）的颜色相对更暗（黑色）这说明了节点度和聚类系数之间的反本文工作的一个关键动机是开发一个随机网络模型，该模型也可以显示节点度和聚类系数之间的逆相关性，而不是众所周知的ER模型（根据该模型，聚类系数与节点度无关）。为了将现实网络建模为ER和THNP模型下的随机图，我们估计理论建模网络中任意两个节点之间的链接（plink）概率为KRwG/N1，其中KRwG和N分别为顶点的平均度和总的真实世界网络中的节点数。图8展示了plink和分析指标相对于六个真实网络的平均度的比较我们观察到p链接和平均相关系数随着平均度的增加而减小;而节点度的平均路径长度和谱半径比似乎几乎与平均节点度无关。4.4. 邻近度评价在本节中，我们评估THNP和ER模型下理论生成的随机图与相应的现实网络的接近性（相似性）。我们使用任意两个节点之间链接的估计概率（如3.3节所述估计）和真实世界网络的节点数来生成THNP和ER模型下的相应随机网络。对于每个真实世界的网络（节点数量和估计的p链路值作为参数），我们生成了100个随机网络实例（在两种模型中的每一种下：THNP和ER），并对分析指标的值进行平均。对于每个真实世界的网络和相应的两个随机网络，我们评估了分析指标（度，聚类系数，路径长度和节点度的谱半径比）的平均值和分布，只要适用。图图9和图10分别显示了随机网络在THNP和ER模型下的分析度量的平均值与在真实世界网络下获得的平均值的接近程度。我们观察到THNP模型生成的随机网络的平均聚类系数与相应的现实世界网络的平均聚类系数非常一致（在六种情况中的四种情况下），而ER模型下生成的随机网络的平均聚类系数与我们还观察到THNP模型的随机网络表现出相对较大的值为节点度的谱半径比（与ER模型相比），并招致SPR值相对更接近现实世界的网络。权衡是THNP模型随机网络的平均路径长度略大于对应的真实世界网络和ER模型随机网络所获得THNP模型随机网络的平均节点度值略小于相应的真实世界网络和ER模型随机网络的平均节点度这归因于使用两跳邻居的三角闭合的偏好（如在图1所示的示例中观察到的）。 4）。注意，涉及三个节点（比如节点u、v和w）的三角形闭合可以促进涉及这三个节点中的任何两个的一跳的路径我们观察到，对三角形闭合的偏好（而不是添加链接来任意连接任何两个节点）只会增加观察到网络中任何两个节点之间更大路径长度的机会。图图11示出了在THNP和ER模型下生成的随机网络与对应的真实世界网络的相对接近度的定量比较。接近度值使用Eq.（1）关于度、聚类系数、路径长度和节点谱半径比四个分析指标的平均值具有高聚类系数的随机网络图模型397平均学位与链接平均度的估计概率与平均集聚系数美国足球网（FN）美国政治图书网（PN）空手道网络（KN）C. Elegans神经网络（CN）悲惨世界网络（LN）美国机场网络（AN）图7真实世界网络的可视化（度与聚类系数）。平均学位与平均路径长度平均度与光谱半径比：节点度图8基于估计的链接概率和分析指标的真实网络比较。℃下理想的接近值是0;我们观察到THNP模型产生的接近值对于分析的六个真实世界网络中的五个小于0.5，并且小于0.25六家电视网中的三家另一方面ER模型引起大于0.5的邻近值所有六个真实世界的网络分析。对于六个真实世界网络中的五个，ER模型下的随机网络的邻近值比THNP模型下的随机网络的邻近值大2-7倍。我们还观察了THNP模型为了非常接近在节点度上表现出适度变化的真实世界网络（即，对于在1.1-1.5范围内的真实世界网络的节点度值的谱半径比这些是现实世界网络的类别（如政治书籍网络和空手道网络），它们既不是完全随机的，也不是完全无标度的，并且ER模型或Barabasi-Albert（BA）模型[4]无法有效地对它们进行建模。这就是拟议的THNP模型的用武之地。它可以有效地模拟随机网络，398N. Meghanathan等人度聚类系数路径长度 谱半径比节点度图9真实世界网络和THNP模型下生成的相应随机网络的接近度的可视化（基于分析指标）。度聚类系数路径长度谱半径比节点度图10真实世界网络和在ER模型下生成的相应随机网络的接近度的可视化（基于分析度量）。图11THNP和ER模型下的随机网络与相应现实世界网络的接近度的定量评估（基于分析指标）。尾部和/或较长的头部（即，那些看起来像随机网络和无标度网络的组合的网络）。图图12（a）-（f）示出了针对真实世界网络（在图中缩写为RWG）和在THNP和ER模型下生成的相应随机网络（在所有100次试验中计算）获得的分析度量（度、聚类系数和路径长度）的分布。我们得到一个特定网络图的度和路径长度的概率分布如下：我们计算遇到度量的特定值的实例数。在度的情况下，实例的数量是展示度的特定值的节点在路径长度的情况下，实例的数量是节点对之间的最小跳数在最短路径上的是测量的路径长度。观察到特定网络的分析度量（度或路径长度）的特定值的概率是引发特定值的实例数除以观察到的实例我们观察到基于THNP模型的随机网络的度分布和路径长度分布相对于基于ER模型的随机网络更平坦和更宽。我们将此归因于在基于THNP模型的随机网络的情况下观察到的节点度和路径长度的较大变化尽管如此，度分布和路径长度分布都表现出泊松分布[1]，正如在基于ER模型的随机网络中所观察到的那样。同样，THNP-随机网络可以被解释为仍然表现出小世界属性[13]，因为观察到的平均路径长度仅比真实世界网络和相应的ER-模型随机网络中观察到的平均路径长度多20%为了获得度与聚类系数的分布，我们确定了表现出特定节点度值的顶点我们观察了基于THNP模型的随机网络图的聚类系数的分布，以模拟对真实世界网络观察到的聚类系数随着节点度的增加而减小），并且与针对这些网络观察到的值紧密对齐另一方面，正如预期的那样，在基于ER模式的随机网络中观察到的节点的聚类系数为具有高聚类系数的随机网络图模型399(a) US Football Network（FN）：节点度的谱半径比-1.01(b) US Politics Books Network（PN）：节点度的谱半径比-1.41(c) Karate Club Network（KN）：节点度的谱半径比-1.46(d) C. Elegans Network（CN）：节点度的谱半径比-1.68(e) 悲惨世界网络（LN）：节点度的谱半径比-1.82(f) 美国机场网络（AN）：节点度的谱半径比-3.22图12节点度和路径长度的概率分布，以及节点度与THNP和ER模型下真实网络和随机网络的聚类系数独立于节点度，并且简单地对应于任意两个节点之间的链路的估计概率[3]。5. 结论本文的高层次贡献是一个随机网络图模型的建议，捕捉逆关系，节点度和聚类系数之间的关系，以及在节点度匹配方面表现出相对较大的变化，更接近真实世界的网络，其度分布表现出具有长尾和/或长头的随机网络状泊松曲线。我们通过在随机网络的演化过程中偏好三角形闭合来实现上述连接。节点优先附加到其400N. Meghanathan等人两跳邻居（以便于三角形闭合）而不是任意节点。因此，我们将所提出的模型称为基于两跳邻域偏好（THNP）的随机网络模型。THNP模型非常适合于对现实世界的社交网络建模，其中主要基于两跳邻域信息（如Face-book中的Friends of Friends）来发起关联（如Facebook中的THNP模型还结合了这样的特征，其中节点更喜欢连接到具有大量公共邻居的两跳邻居。这对应于Facebook中的场景，其中用户更有可能接受来自具有几个共同好友的用户的好友请求。与相关工作部分中讨论的模型不同，THNP模型不需要任何顶点的度序列（包括单边度序列或三角度序列），这些度序列太耗时而无法确定并用于生成随机图。THNP模型可以在只知道真实世界网络图中的顶点数和边数的情况下我们观察到基于THNP模型的随机网络表现出更高的平均聚类系数和节点度的谱半径比（相对更接近真实世界的网络）和略小的平均节点度。与真实世界网络相比，权衡是平均路径长度的适度增加基于THNP模型的随机网络与真实世界网络的接近度值显著较低（即，THNP-随机网络相对更接近真实世界网络）据我们所知，所提出的THNP模型是第一个这样的随机网络模型，其中节点的聚类系数随着节点度的增加而减少（如在现实世界的网络中），并且仍然表现出泊松式的度分布。在这些方面，我们是一个重要的努力，从随机网络的角度来看现实世界的网络。确认这项工作是由美国杰克逊州立大学的Massie ChairGrant（#：DE-NA 0000654）资助的引用[1] 放大图片作者：JH.概率方法。第3版Wiley-Interscience;2008年。[2] 博略巴斯湾随机图。剑桥大学出版社;2001年。[3] 纽曼M.网络：介绍。牛津大学出版社; 2010年。[4] 作 者 声 明 ： John M. 随 机 网 络 中 的 标 度 现 象 。Science1999;286（5439）：509-12.[5] ErdosP ， RenyiA. 关 于 随 机 图 I.PublicationesMathematicae1959;6：290-7.[6] Meghanathan N谱半径作为复杂网络图节点度变化的度量。第三届数字内容与应用国际会议论文集，海南，中国。p.30比3[7] 雷·DC雷·SR麦克唐纳·JJ线性代数及其应用。第5版，Pearson Publishers;2015年。[8] Butler BK，Siegel PH.非负矩阵和有向图的谱半径的Sharpbounds。Linear Algebra Appl 2013;439（）：1468-78.[9] 纽曼 M. http://www-personal.umich.edu/~ mejn/netdata/>，[last accessed：November 13，2015].[10] Pajek 数 据 集 。 ，[最后访问时间：2015年11月13日]。[11] 切文湾掌握Gephi网络可视化。PacktPubl-lishing; 2015.[1
我的内容管理
展开
