社会网络分析与社区结构的影响:马尔可夫模型、FSA算法、社交网络路径长度预测

E. Σ沙特国王大学学报社团结构对Himansu Sekhar Pattanayak，Harsh K.阿姆里特？拉尔？桑加尔？维尔马印度新德里阿提奇莱因福奥文章历史记录：收到2020年2020年10月16日修订2020年10月18日接受2020年10月22日在线提供保留字：社区检测社会网络分析复杂网络图挖掘概率计算马尔可夫模型FSA算法平均路径长度A B S T R A C T社区结构是在各种社交网络中观察到的一种普遍现象。在这项工作中，一个新的社区发现算法提出了通过估计社区结构的影响，平均路径长度的网络。Erdos-Renyi图模型被用来作为一个参考，计算由于社区形成的网络的平均路径长度的变化。通过人工网络的实验，发现社会网络中的社区结构有助于延长平均最短路径长度。随机图的平均最短路径长度小于具有社区结构的社会网络。与包含相同数量的节点和边的随机图相比，随着单个社区的大小增加，平均最短路径长度的差异减小这种关系被用来预测网络中的平均社区规模及其数量。上述研究结果已应用于所提出的算法。所提出的社区检测算法是对火灾蔓延社区检测算法（Pattanayak，2019）的增强，其中自动计算R半径邻域子图的R值。©2020作者由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍社交网络是由各种实体以及它们之间的相互联系构成的。实体可以是移动节点、人、组织、动物和网页。虽然在文献中有各种各样的技术来表示社会网络，但图论概念被广泛使用（Wasserman，1994）。在社交网络的图表示中，实体成为节点，并且这些实体之间的现实世界中的网络以前被认为是随机图（Erdos，1960）。一个随机图是一个由N个节点和E条边组成的图，其中N条可能的边中的每一条都有相等的概率被选为图的边。随着网络科学的不断发展，人们发现现实世界的社交网络和生物网络不同于随机图。这些网络*通讯作者。电子邮件地址：himansusekharpattanayak@gmail.com（H.S. Pattanayak）。沙特国王大学负责同行审查制作和主办：Elsevier遵循链路的幂律分布，其中只有少数（Barabási和Albert，1999）节点共享大部分网络链路并充当枢纽。社区结构是一种较新的现象（Girvan，2001），其中网络的一些节点在本地形成社区。在社区中，参与节点大多在自己内部连接，与外部节点的链接较少。1.1. 网络的社团结构与平均路径长度社交网络的直径较小，参与节点之间的平均路径长度也较短，正如作者所解释的那样（Barabási和Albert，1999）。大多数社交网络确实表现出偏好性依恋和社区结构.与社区结构有助于缩短平均路径长度的信念相反，我们发现社会网络中的社区结构导致参与节点之间的平均最短路径长度延长（Sallaberry et al.，2013年）的报告。这是一个彻底的分类，下面给出了一个例子，有四个网络具有社区结构。图1、图2、图3和图4中示出了四个图，每个图包含12个节点。图1所示的图有14条边和三个大小相等的社区该图的平均路径长度图中所示的图表。 2https://doi.org/10.1016/j.jksuci.2020.10.0141319-1578/©2020作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comHimansu Sekhar Pattanayak，H.K.维尔玛和阿姆丽特·拉尔·桑加尔沙特国王大学学报8402Fig. 1. 图为三个社区。图二.图为两个社区。Himansu Sekhar Pattanayak，H.K.维尔玛和阿姆丽特·拉尔·桑加尔沙特国王大学学报8403图三. 一边重新连接。见图4。 两条边重新连接。Himansu Sekhar Pattanayak，H.K.维尔玛和阿姆丽特·拉尔·桑加尔沙特国王大学学报8404表1平均最短路径长度。图数量的节点边数平均路径长度图-112143.272727272727273图212133.0图312132.8484848484848486图412132.696969696969697有13条边和两个大小相似的社区（每个社区有6个节点）。该图的平均路径长度为3.0。通过用连接节点4和1的新边替换连接节点4和节点5的边来破坏图2的社区结构，如图3所示。该图的平均路径长度为2.84848484848486。图4所示的图具有与前面的图相同的边数（13条边），但是社区结构被进一步破坏;边（9，10）被边（7，10）代替该图的平均路径长度现在减少到2.6969696969697（表1）。随着网络中社区结构和社区数量的减少，网络的平均路径长度增加。这种网络结构特性的变化，对群落形成的影响将被调查、量化，并用于群落检测，作为我们的拟议工作。1.2. 动机和主要贡献虽然人们对社区发现算法的设计及其应用进行了大量的研究，但对社区形成对网络整体结构的影响进行的本文详细分析了社区形成对网络结构的影响，特别是对网络平均最短路径长度的影响，这将有助于量化社区结构对网络的影响。所提出的工作探讨了社区形成对网络的结构影响，并将这些发现应用于设计一个有效的社区检测算法。提出的社区检测算法可用于本地级和网络级社区检测。所提出的算法也可以与重叠的社区。本工作的重要贡献概括如下：1. 提出了一种新的基于概率的方法，仅用节点数和边数作为参数来预测Erdos-Renyi图（随机图）该方法比传统的Dijkstra2. 通过详细的研究，建立了社团结构与网络平均路径长度之间的关系。具有社区结构的网络具有平均路径长度比具有相似数目的节点和边的随机图长。这种关系被用来估计社区形成对网络结构的影响。3. 研究了社团平均大小对平均路径长度的影响，提出了一种预测网络平均社团大小和社团数的新方法4. 提出了一种新的利用社区平均大小和社区成员矩阵的社区发现算法。提出的社区检测算法可以用于本地社区检测和网络级社区检测。该算法也能够与重叠的ping社区。该算法不需要关于网络中存在的社区数量的用于计算网络平均最短路径的快速概率该文件的研究结果也可能有助于分析和设计网络。本文的其余部分按以下方式组织。第二节对相关文献进行了综述。在第三节中，我们提出了一种用概率方法求Erdos-Renyi随机图的平均最短路长的快速有效的方法。在我们的工作中使用所提出的方法来计算平均最短路径长度。第四节研究了社区结构与平均最短路径长度之间的关系。第5节分析了社区平均规模和节点度对平均最短路径长度的影响。 在第六节中，预测了任意两个社区成员节点之间的最短路径的长度。在第七节中，提出了一种新的社区检测算法。在第8节中，通过将所提出的算法与一些众所周知的社区检测算法进行比较来评估该算法。从第3节，第4节，第5节和第6节获得的结果用于第7中提出的社区检测算法。2. 相关工作本文研究了社会网络的结构特性，提出了一种新的社区发现算法。因 此 ， 分 别 讨 论 了社 交 网 络 的 各 种 生 成 模 型 （Hocine Cherifi ，2019），社区检测算法和局部社区检测算法。2.1. 社交网络用于描述社交网络的主要图模型之一是随机根据该模型，一个有n个节点和m条边的网络，通过n个节点之间的随机均匀配对产生m对边。另一种ER模型（Gilbert，1959）确定了每对边之间的相等概率的节点。节点的度分布服从二项分布。Molloy和Reed（1995）提出的构形模型是对ER模型的改进，ER模型中节点度的顺序是预先定义的。标准随机块模型（SBM）（Holland等人，1983）假设节点被分离为块，并且节点之间的边是随机且均匀的。在SBM模型中，块内的节点被假设为相似的，在现实世界中很少如此。SBM模型的一个改进是度相关模型（Karrer和Newman，2011），它根据节点度整合了每个块内节点的异质性。（F，2001）提出的种植分区模型是SBM模型的一个变体。在这个模型中，有两个固定概率，分别定义为p和q。p是块内边缘的概率，q是块间边缘的概率。p > q表示平行结构，而p q表示分离结构。度相关种植分区模型（ME，2016）包含了每个块内节点的度异质性。2.2. 社区发现算法传 统 的 通 信 检 测 算 法 大 多 采 用 模 块 优 化 和 电 导 优 化 作 者（Newman，2006 b）使用了一些公开可用的数据集，并执行谱聚类来检测这些数据集上的社区。谱聚类是通过计算图Himansu Sekhar Pattanayak，H.K.维尔玛和阿姆丽特·拉尔·桑加尔沙特国王大学学报8405网络的Laplacian矩阵根据图形拉普拉斯矩阵，计算Fiedler向量并将其用于分区。fie-dler向量是具有第二小特征值的特征向量该方法使用模块化评分函数。（Andersen，2006）是比简单的光谱聚类改进的技术。这项工作是基于找到一个切附近的一个给定的种子节点。该算法是寻找网络局部社区的一种有效算法该任务使用电导分数而不是在（Blondel，2008）的工作也是基于模块化评分的优化。每个节点都被初始化为一个社区。更大的社区由更小的社区组成由于该算法重复 加 入 较 小 的 社 区 ， 它 是 有 用 的 多 分 辨率 社 区 结 构 的 检 测 。（Wang，2011）中的社区检测是基于这样的想法：在任何社交网络中，只有1%的节点是最活跃的节点，其他节点都连接到这些节点。在（Clauset et al.，2004年）。它通过合并较小的社区来优化模块化得分该算法对分层社区发现有一定的实用价值尽管模块性得分被用于许多社区检测算法中，但模块性得分在发现较小规模的社区时存在缺陷，如（Mrsato和Barthelemy，2007）中所述。作者在（Lancichinetti等人， 2009年，他提出了一个共同的...分层重叠社区结构的社区检测算法。该算法通过优化节点的适应度值在网络的局部层次上运行，并选择最高适应度值的节点。在（Chen etal.，2010年）。另一种算法依赖于传播的节点标签，以找到重叠的社区，在（格雷戈里，2010年）]中描述。节点将它们的标签广播给邻近的节点。选择同意特定节点标签的最大节点作为社区节点。Gopalan和Blei在2013年提出的算法使一个参与者节点能够同时成为多个社区的一部分，作者使用贝叶斯模型。在（Gong等人，2012; Pizzuti，2017; Shi等人，2012; Zhou等人，2016）使用进化方法来检测社交网络中的社区。作者在（Amiri等人，2013）已经考虑了使用Firefly算法进行社区检测的Pareto最优解。在（ Rahimi et al. ， 2018; Gong 等 人 ， 2014 年 ） 。 在 （ Samie 和Hamzeh，2017）中，作者采用了两阶段技术进行社区检测。在该算法的第一阶段中，使用全局信息检测较大的社区，并且在第二阶段中，使用局部信息从已经检测到的较大社区中检测较小的社区。Seshadhri 等人， 2012 ）假设网络的社区是网络的Erdos-Renyi（ER）子图。因此，作者的目标是通过检测ER子图来检测社区作者（Staudt和Meyerhenke，2016）在大型网络上使用并行计算进行社区检测。作者在（庞斯和拉蒂默，2006年）]，使用随机游走模型来识别社区。作者在（Yang和Leskovec，2015）中采用了页面排名半字节和随机游走模型进行本地社区检测。作者根据节点的连通性将社区评分功能分为四个不同的组在（Pattanayak等人， 2019年），作者使用火灾传播模型来寻找社会网络中的社区。该算法还可以检测特定种子节点的本地社区（Vinícius da Fonseca Vieira，2020）中的作者使用435种方法真实世界和合成网络。在（Raganato和Hric，2016）中提出的工作强调了许多社区检测算法的优点和缺点以及它们的可用性，并建议将社区视为顶点与子图共享边的概率。2.3. 局部社区检测算法一些社区检测算法基于找到特定节点周围的本地社区，称为本地社区检测算法。由Yakubi和Kanawati（Yakoubi和Kanawati，2014）提出的被称为LICOD的本地社区检测算法选择领导者节点和与领导者节点连接的其他社区节点以创建社区。Local-T社区检测算法（Fagnan，2014）是一种随机选择初始节点并搜索最高度节点的本地检 测算法， 其他成员节 点被添加 到公共 traids 上。 ENBC（Biswas andBiswas，2015）算法也使用类似的概念进行本地社区检测。Lim和Datta（Lim，2013）提出的算法通过考虑内部和内部连接来在（Tabarzad和Hamzeh。2017），作者提出了一种基于启发式方法的局部社区检测算法。该算法检测早期不稳定的社区，并结合这些社区的检测过程。在（Wenjian Luo，2020）中提出的局部社区检测算法从给定节点开始，随后基于具有更大中心性的最近邻居添加其他该算法声称可以检测多尺度的本地社区。所提出的算法（Kun Guo，2019）使用节点之间的内力来扩展种子节点的社区。与其他专注于寻找更高度节点作为种子节点的社区检测算法不同，（Asgarali Bouyer，2020）中提出的算法首先将标签分配给较低度节点，并通过组合较小的社区形成较大的社区。3. 求随机图平均最短路长的算法在这一节中，提出了一个算法来预测一个有N个节点和E条边的随机Erdos- Renyi图的平均最短路长，而不需要构造图和计算每对节点之间的距离。为了使用Erdos-Renyi图的平均最短路径长度，从一个图读取是不够的。我们需要创建l个Erdos-Renyi图，每个图有N个节点和E条边，并取平均值。然而，这里讨论的所提出的算法，是一个简单的方法来近似平均最短路径长度使用概率方法。虽然经典的近似方法如宽度优先采样（BFS）可以减少获得网络平均路径长度所需的时间，但该方法的 效 率高 度 依 赖 于 初 始 节 点 ， 并 且 容 易 出 现 不 准 确 的 估 计（Matsumura，2018）。一个有N个节点和E条边的随机图，平均节点度d计算为d =（2/E）/N。因此，图中的每个节点平均可以用直接链接链接到d个其他节点（来自N-1个可用节点，因为不允许自边为了计算平均最短路径长度，我们从一个源节点开始;概率地计算它到所有其他节点的距离（源节点到图中任何其他节点之间的预期距离）。为了简化计算，假设所有节点的度相同在1-边距离处的节点（邻居节点）的数量最初被估计同样，节点数Himansu Sekhar Pattanayak，H.K.维尔玛和阿姆丽特·拉尔·桑加尔沙特国王大学学报8406------ -一种--- - -一种D在2边，3边，... . 估计R边（1/4RN<.t A ×。N-T-T-A-1并计算平均最短路径长度3.1. 与源节点一个新1/4老 联系我们d-kK. N-T-1型ð5Þ假设每个节点都连接到图的其他d个因此，源将具有d条具有1-边的路径T的值更新为T+t，t的值更新为t=A。算法1：随机图的平均最短路径长度距离（平均）。这d个节点中的每一个都会连接到d-1其他节点（一个链路已用于连接到源节点）。在1-边距离处的d个节点预期与d（d1）个具有边的其他节点连接。然而，并非所有d（d1）条边都连接到不同的新节点，这意味着一些边来自与源相距1-边距离的d个 在这种情况下，少于d（d-1）个节点与源具有2-边距离。3.2. 距源节点R边距离处的节点数设T是已经有d个连接并且不会参与任何新连接的节点数，t是以（R-1）-边距离连接到源的节点avg_shortest_path_len_random（N，E）：数据：节点数=N，边数=E结果：平均最短路径长度d =（2*E）/N，t = d，T = 0，s =d，而i的范围从2到N-1。如果（N-T-11），则：breakelse：A=0end if而j在1到t的范围内：而范围1到d中的k为：.tA×。N-T-T-A-1(forR N的任何整数值）。源节点连接对于d个相邻节点，T的值变为1，并且t的值变成D。设A是已经与源节点以距离R连接的不同节点的数量。对于t个节点中的任何特定节点，该节点可以连接到1个新节点和d 1个旧节点（已经连接到源的节点）或2个新节点和d2个旧节点，以此类推。d-k个旧节点由等式给出。（一）..t A ×。 N-T-T-A-1A¼A×end whileend whileT=T+tt=As=s+i*tend whilereturn s/（N-1）d-kK. N-T-1型d-k k其中t+A是旧节点（已经具有到源节点的路径的节点）的可能数量，N T t A1是新节点的可能数量，因为N-1是节点（不包括源）的总数，T是已经具有d个邻居的节点的数量，t是距源d-1距离处的节点的数量，并且A是已经与源节点连接（在距离R处）的新节点的数量对于尚未与其他节点连接的节点，可能出现的边的总数在等式中给出（二）：. N-T-1双头 2双头其中N T 1是可能连接的节点数，d是特定节点的边数。因此，连接到k个新节点和（d-k（3）：. t A ×。N-T-T-A-1最后通过一个实例说明了该算法。 给定的图（图5）是一个具有20个节点和65条边的Erdos-Renyi随机图。平均值为6.5。d的值转换为最接近的整数是6。t的值表示距离源R（此处R= 1）处的链路数，初始化为6。T值表示已经具有d个链路并且将不参与任何新链路的节点（源节点除外）的数量，该值初始化为零。s的值，其表示源对于R= 2;t=10.5849，T= 6，s= 27.1699。对于R= 3;t= 1.5723，T= 16.5849，和s= 31.8870。 对于R= 4;t= 0，T= 18.157327769833987，和s= 31.8870。当t的值变为0时，算法停止。 现在，平均最短路径计算为s/19 = 1.6782。使用Dijkstra算法计算的平均最短路径为1.6844。误差百分比为0.36764。虽然t和T的值是整数值;但是这些值可以在以下期间取分数值：执行算法。d-kK. N-T-1型双头机用于评估计算平均值本文利用Erdos-Renyi图模型构造了10个随机图，并求出了网络的最短路长现在，由与源相距R边距离的任何节点连接的新节点的预期数量由等式给出。（四）：.t A ×。N-T-T-A-1对于所有这些图，使用全对最短路径算法来计算。每个实验迭代十次执行，并考虑平均值。然后将所得结果与计算的平均最短路径长度进行比较k×d-kK. N-T-1型双头机使用该算法。结果见表2。使用该算法近似类似于使用全对最短算法计算的平均路径长度。最大的差异，其中k的值的范围从1到d。A的值更新为：值仅为2.14%，因此建议的方法用于DDD3ÞD4ÞHimansu Sekhar Pattanayak，H.K.维尔玛和阿姆丽特·拉尔·桑加尔沙特国王大学学报8407-图五. 一个具有20个节点和65条边的Erdos-Renyi随机图。表2使用所提出的算法预测的平均最短路径长度。节点边缘建议算法的值最短路径算法差异百分比1804503.43823.41070.80832567973.41233.40920.08982709583.13563.06962.149027010802.92632.90910.591540016923.00993.037170.895339618672.94202.90211.373339620172.84772.81901.017340322272.75122.74870.090439222722.74562.69711.798340525322.64892.648990.3117其他路段平均最短路径长度的计算。4. 群落结构与平均最短路径长度的关系本节评估了社区结构与平均最短路径长度用于这项工作的网络是由 20 个 社 区 的 400 个 节 点 组 成 的 Relaxed Caveman 和 PlantedPartition通过改变边重布线概率（每条边重布线以连接到不同社区的概率）从0. 05比1 0.种植分区图包括通过改变社区间节点-链路概率从0. 002到0。04. 在松弛洞穴人图和种植划分图中，分别通过增加边重连和社区间节点连接概率，使社区结构相关数据见表3&4. 每个表的列是节点数、边数、社区（每个图固定20个社区）、平均节点度、随机图的平均路径长度（具有相等数量的节点和边）、研究中的图的平均路径长度、平均路径长度的差、分数中的平均路径长度的差（计算为[平均路径长度rand路径长度/rand路径长度]）以及每个平均度的分数中的使…的影响表3松弛穴居图的群落结构与平均最短路长的关系节点边缘平均度数社区Deg度比通信间问题兰德路径透镜平均路径长度差异分数差异Frac Per Deg40038001918.1050.952894740.052.3381917293.3127192980.9745275690.4167868510.0219361540038001917.0950.899736840.12.3381917292.8271052630.4889135340.2090989920.0110052140038001915.8750.835526320.152.3381917292.6984335840.3602418550.1540685690.00810887240038001914.890.783684210.22.3381917292.6391228070.3009310780.1287024810.00677381540038001914.020.737894740.252.3381917292.5771804510.2389887220.1022109170.00537952240038001913.2150.695526320.32.3381917292.5355388470.1973471180.0844015980.00444218940038001912.4650.656052630.352.3381917292.4956516290.15745990.0673425950.00354434740038001911.420.601052630.42.3381917292.4671177940.1289260650.0551392190.00290206440038001910.640.560.452.3381917292.4567669170.1185751880.0507123460.0026690714003800199.820.516842110.52.3381917292.4205263160.0823345860.0352129320.0018533124003800198.650.455263160.552.3381917292.4016791980.0634874690.0271523790.0014290734003800197.990.420526320.62.3381917292.3842606520.0460689220.0197027990.0010369894003800197.2050.379210530.652.3381917292.375476190.0372844610.0159458530.0008392554003800196.310.332105260.72.3381917292.368395990.0302042610.0129177860.0006798834003800195.570.293157890.752.3381917292.3592731830.0210814540.0090161360.0004745334003800194.6550.2450.82.3381917292.3515789470.0133872180.0057254580.000301344003800193.990.210.852.3381917292.345563910.007372180.0031529410.0001659444003800193.2250.169736840.92.3381917292.3438345860.0056428570.0024133420.0001270184003800192.2550.118684210.952.3381917292.3435614040.0053696740.0022965070.0001208694003800191.6150.08512.3381917292.3422087720.0040170430.0017180129.04217E-05Himansu Sekhar Pattanayak，H.K.维尔玛和阿姆丽特·拉尔·桑加尔沙特国王大学学报8408表4人工林划分图中群落结构与平均最短路径长度的关系节点边缘平均度数社区Deg度比通信间问题随机路径透镜实际光程透镜差异分数差异每度压裂400299014.9514.2350.95090180.0022.515167923.6186340851.1034661650.438724650.02934613400310715.53514.1550.906500160.0042.4879498753.0924686720.6045187970.2429786880.015640727400333116.65514.250.85176330.0062.4378609022.8715538850.4336929820.1778989860.010681416400343917.19514.110.827080890.0082.4135050132.7581203010.3446152880.1427862330.008303939400358617.9314.3950.790065860.012.3827944862.6642982460.2815037590.1181401760.006588967400375318.76514.240.762312630.0122.3482393482.6032832080.255043860.1086106750.005787939400399019.9514.1750.723214290.0142.3009298252.5217669170.2208370930.0959773260.004810894400405620.2814.250.700762230.0162.2883471182.4953132830.2069661650.0904435190.00445974400418220.9114.3150.674599430.0182.2645250632.4458145360.1812894740.0800562890.003828613400436621.8314.1750.649931220.022.2320864662.4039223060.171835840.0769844010.003526542400448722.43514.340.635497450.0222.2107431082.3723182960.1615751880.073086370.003257694400462523.12514.070.608300910.0242.1884887222.3345739350.1460852130.0667516410.002886557400483824.1914.3350.593336090.0262.1576453632.2839724310.1263270680.0585485780.002420363400498824.9414.440.573357160.0282.1349786972.2525313280.1175526320.055060330.002207712400512625.6314.2250.551142970.032.116083962.2175814540.1014974940.0479647760.001871431400536826.8414.030.538372990.0322.0858909772.1743609020.0884699250.0424134940.001580235400544527.22514.060.527085290.0342.0766954892.1566290730.0799335840.0384907580.001413802400558027.914.2550.514992770.0362.0628684212.1338847120.0710162910.0344259920.001233907400572628.6314.3150.493705810.0382.0464674192.1124185460.0659511280.0322268150.001125631400593729.68514.2350.480506330.042.0265112782.0836591480.057147870.0282001240.000949979平均节点度对平均路径长度的影响，计算平均路径长度的差异，并在图中给出。 6和图7.第一次会议。 图在图6中，x轴是边缘重新布线概率，y轴是平均最短路径长度的差，以每平均度的分数表示。在图7中，x轴是社区间节点-链路概率，y轴是平均最短路径长度的差，以每平均度的分数表示。 蓝色虚线表示两个图中的实际数据点，而红色实线表示近似线（y = 0）。002/x，y = 0。图中的00015/x。7）。从表3和表4可以看出，对于每个图，平均路径长度大于具有相等节点和边的随机图的平均路径长度。随着社区结构的扭曲，每度的平均路径长度的差异是也减少了。 从图图&6 7，可以得出结论，每度平均最短路径长度的差异与网络中的社区结构成反比。群落大小保持恒定，使得由于额外的参数而不会为分析引入额外的复杂性;因此，将松弛的穴居人和种植分区图用于实验，因为它们具有均匀的群落大小。5. 平均社区规模与平均最短路径长度的关系在本节中，我们将分析网络的平均路径长度与社区数量、社区平均大小和节点平均度之间的见图6。 由于松弛Caveman图的社区结构，每度的平均路径长度存在差异。Himansu Sekhar Pattanayak，H.K.维尔玛和阿姆丽特·拉尔·桑加尔沙特国王大学学报8409见图7。由于种植分区图的群落结构，每度的平均路径长度存在差异。5.1. 社区数量和平均最短路径长度绘制了一个线图（图）。图8），其中社区的数量作为X轴，并且每个平均度的平均最短路径长度的差异（与具有相等节点和边的随机Erdos-Renyi图相比）作为y轴。的数量群落从2个到40个不等。图8示出了松弛穴居人和种植分区图的图。蓝色虚线表示Relaxed Caveman图，红色虚线表示Planted Partition图。与图8相关的数据呈现在表5和表6中。对于所有这些图，节点的数量约为400。从图8中可以推断出，见图8。 由于没有社区，每度的平均最短路径长度存在差异。Himansu Sekhar Pattanayak，H.K.维尔玛和阿姆丽特·拉尔·桑加尔沙特国王大学学报8410×表5松弛Caveman图的平均社团大小与平均最短路长关系。节点边缘平均度数通信数量通信大小兰德路径透镜实际路径长度差异分数差异每度压裂18045053063.4143078836.7635630043.3492551210.9809470130.19618940324573563573.2628931085.6660421552.4031490470.7365086650.12275144425689673283.0566084564.9101715691.8535631130.6064116940.086630242270108083092.9121822944.8248106841.912628390.6567680860.0820960114001800940102.9600027854.3156015041.3555987190.4579721090.0508857939619801036112.8370144484.2244725741.3874581260.4890557140.04890557139621781133122.7450722414.0304053191.2853330780.4682328790.04256662540324181231132.6793760723.654333790.9749577180.3638749060.03032290940626391329142.6201666363.4328042330.8126375970.3101472960.02385748440528351427152.566266963.4129079570.8466409970.3299115060.02356510840030001525162.5128233083.251416040.7385927320.2939294340.01959529639131281623172.4578647783.1455177390.6876529610.2797765630.01748603539633661722182.4183582663.0877892850.6694310190.2768121780.01628306939935911821192.3778189192.9319655920.5541466730.2330483070.01294712840038001920202.33791982.8349373430.4970175440.2125896470.01118892939939902019212.2977279882.7749272680.477199280.2076831030.01038415539641582118222.257362232.7667945280.5094322980.225675920.01074647240846922317242.2022137112.7205039260.5182902150.2353496450.01023259340048002416252.1620451132.6762531330.514208020.2378340850.00990975439056552913302.0317685062.5363654340.5045969280.2483535540.00856391639669303511361.9522669742.4132591740.46099220.2361317420.00674662140078003910401.9217431082.3479824560.4262393480.2217982970.0056871364009800498501.8792644112.1651002510.285835840.1520998520.00310407940015,800795801.8020050131.8354636590.0334586470.0185674550.00023503140019,8009941001.7518796991.7624686720.0105889720.0060443496.1054E-0540039,80019922001.5012