沙特国王大学学报NI-Louvain：一种基于影响分析Dipika Singha，Rakhi Gargba宾夕法尼亚州瓦拉纳西Banaras印度大学科学研究所计算机科学系。邮编：221005b巴拉纳西Banaras印度大学Mahila Maha Vidyalaya计算机科学系。邮编：221005阿提奇莱因福奥文章历史记录：2021年2月13日收到2021年6月13日修订2021年7月9日接受2021年7月15日在线提供保留字：Louvain模糊隶属度离群点检测A B S T R A C T社区发现是社交媒体挖掘的一个重要研究领域已经开发了许多算法然而，现有的算法大多没有考虑组中每个节点的影响，这可能是不同的，可以影响社区检测的结果。在本文中，我们提出了一种新的基于Louvain算法命名为“NI-Louvain”，它考虑了每个节点在一个组中的影响，不仅检测社区，而且在社区中最有影响力的节点。该算法分为三个步骤。首先，对输入图进行处理以降低其密度。这是通过从图中计算集团来完成的第二步，将Louvain的多级算法应用于该团图。得到的社区具有更好的模块化值比现有的算法，如边缘介数，标签传播，领先的特征，Louvain，快速贪婪，walktrap，和信息地图。在第三步中，结果社区的节点被转换回原始图的节点。该步骤有利于检测重叠社区、每个节点的模糊成员、所形成的每个社区中的最有影响力的节点以及离群节点。版权所有©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍随着互联网的兴起，像Facebook、Twitter、Instagram等社交网络已经成为我们日常生活中不可或缺的一部分。这些社交网络由人和他们之间的互动组成。它可以被表示为一个图，其中人可以被视为节点，他们的交互作为边。在这些图中，某些子图之间的交互作用比其它子图多.这些子图被称为社区（Chaanato和Hric，2016）。基本上，一个特定社区的成员具有一些共同的属性，这些属性不同于其他成员。这些社区在分析时显示出显著的结果。社区检测是指在网络中发现社区。这是一个重要的研究领域它在Recom中有着广泛的应用*通讯作者。电子邮件地址：dipikaa. gmail.com（D. Singh）。沙特国王大学负责同行审查修正系统、异常检测、异常值检测、欺诈检测、谣言或假新闻检测、疾病检测等，因为其将志同道合或相似的事物分组在一起的特性（Javed等人， 2018年）。已经开发了许多社区检测算法来展开社区中的信息（Wang等人，2015年）。这些算法遵循不同的社区发现方法，如分层分裂，分层凝聚，随机游走等。模块性是衡量不同算法形成的社区质量的重要指标。较高的模数值表明更好的群落形成（Newman，2006 a;Newman，2006 b）。检测社区的主要挑战是，大多数现有的算法对待社区的所有节点都一样。然而，在现实世界中，人们并不一样。有些人是更积极的参与者，而另一些人则不是。因此，社区的每个成员在社区中都有不同的影响力（Liu et al.， 2020年）。因此，在社区检测时，考虑节点的影响是至关重要的。在本文中，我们提出了一种新的算法，这一拟议办法的主要贡献是：https://doi.org/10.1016/j.jksuci.2021.07.0061319-1578/©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comD. Singh和R. Garg沙特国王大学学报7766由NI-Louvain形成的社区具有比正在考虑的其他现有算法形成的社区更高的模块化值。重叠社区以及每个节点的模糊成员资格。● 检测到离群节点● 确定社区中最有影响力的节点为了优化模型的模块度值，我们研究了图的密度对模型模块度的影响形成的社区。我们发现图的密度与所形成的社区的模块度成反比。因此，我们进一步处理了图以降低其密度。为此，我们应用团渗透方法来得到一个图（Derényi等人，2005年）。这个团图具有比原始图更小的密度。现在，Louvain的多级算法被应用到团图中以获得社区。经过实验，我们得到了一个更好的模块化值比社区形成的算法，如边缘介数，标签传播，领先的特征，鲁汶，快速贪婪，walktrap和信息地图算法。然后，团图社区的节点被替换回到它们相应的组成节点。通过这种方式，我们计算不同节点的成员值，这有助于找到重叠社区，模糊成员，最有影响力的节点和离群节点，这些节点在上述任何现有算法中都没有计算。本文的其余部分组织为：第2节讨论了一些关键的相关工作，在社区检测。在第3节中，我们讨论了社区检测的概念，以更好地理解这个概念。在第3节中讨论了新提出的算法。在第四节中，我们讨论了我们的实验结果。 第五讨论了实验的局限性和未来的工作。第六部分是本文2. 相关工作边缘介数是由Girvan和Newman提出的，它遵循分层划分方法（Girvan和Newman，2002）。它通过逐步从原始网络中删除边缘来形成社区。经过某些步骤后，连接的组件变得恒定，这就是所需的社区。它基于边介数的概念。它是通过网络的节点对之间的最短路径的数量。首先计算网络中所有边的介数得分。然后移除具有最高介数分数的边缘。 之后，受移除影响的边的介数得分重新计算。重复该循环，直到没有获得这样的边缘。Clauset等人开发了快速贪婪算法，该算法使用层次凝聚方法并基于贪婪模块化优化的原理工作（Clauset等人，2004年）。在该算法中，首先将每个节点视为一个单例社区。然后逐一检查所有可能的节点对，以提高模块性。具有最高模度改进的节点对被分组在同一社区中。重复这个过程，直到没有社区对合并导致模块化的增加。Newman提出的前导本征值方法遵循分层分解方法，利用模块度矩阵的特征值和特征向量对模块度进行谱优化（Newman，2006 a;Newman，2006 b）。该算法首先构造模块度矩阵然后，给出了模块度矩阵B = A-P，其中A是网络的邻接矩阵，P是具有相同度的随机网络中的两个顶点之间存在边的概率作为被观察的网络然后计算模块度矩阵的首特征向量之后，基于特征向量中元素的符号将图分成两部分。重复上述步骤，直到我们得到相同的特征向量符号，表明没有更多的潜在社区。SpinGlass算法是由Reichardt Bornholdt提出的，它基于统计物理学的方法，并使用Potts模型的原理（Reichardt和Bornholdt，2006）。这里使用的基本概念是，边应该连接相同状态的节点，而不同状态的节点应该断开连接。在这种情况下，确定每对节点的自旋状态。如果节点之间存在边，则它们被认为处于相同的自旋状态;否则处于不同的自旋状态。这个过程重复一定数量的步骤，最终的结果被认为是一个社区。Walktrap是由Pon Latterfly提出的，它使用了聚类的随机游走方法（Pons and Latterfly，2006）。它是从小的随机游动将留在同一社区的想法演变而来的。该算法首先计算相邻结点之间的距离。然后通过合并接近的节点形成社区，并再次计算相邻社区之间的距离。重复这些步骤，直到达到饱和。标签传播由Raghvan等人在2007年提出。它遵循分层凝聚方法，并致力于在网络中传播标签的概念。在这第一个网络中的每个节点都被分配了唯一的标签。之后，标签在网络中传播。在每次迭代中，每个节点都用最大邻居数的标签更新其标签。最后，当每个节点具有其大多数邻居的标签时，算法停止，使得不可能进行新的标签更新（Raghavan等人， 2007年）。最优算法是由Brandes等人提出的，它使用层次凝聚方法，通过优化所有分区的模块度来计算社区结构。该算法首先求解模块度优化问题，得到整数规划问题的方程然后将其发送到GLPK （GNULinear Programming Kit）中进行求解，获得最大模块度.GLPK是一个用C语言编写的软件包，用于解决大规模整数规划问题。GLPK返回每个集群的最大模块化。然后通过考虑GLPK的结果形成社区（Brandes等人， 2007年）。多级算法由鲁汶大学的Blondel等人在2008年提出（Blondel等人， 2008年）。它是一种遵循层次凝聚方法的贪婪优化方法。它包括两个步骤。第一步是局部模态优化步骤。第二步是基于第一步的社区定义一个新的粗粒度网络首先，遍历网络中的每个节点每个节点从其社区中移除然后计算所有受影响节点的模块度如果modularity的否则，该节点将再次分配给其先前的社区。这是重复的，直到社区分配没有变化在第二步中，在第一步中形成的社区被视为称为粗粒度网络的节点。重复这些步骤，直到在后续步骤中得到相同的结果。信息地图是由Rosvall等人提出的，它遵循聚类的随机游走方法。在该算法中，网络被编码成模块，以最大化关于原始网络的信息然后，通过有限容量信道将信号发送到解码器然后，通过解码消息，解码器构建可能候选者的社区（Rosvall等人， 2014年）。传统的社区发现算法的许多变体也被开发出来，它们将机器学习或遗传算法与传统方法相结合。 例如，Wang et al.基于k均值和机器的ELM-CD算法●●D. Singh和R. Garg沙特国王大学学报7767-X.Q.Σ¼--——；;;.Σ学习方法（Wang等人，2018年）。Hosseeini和Rezvanian提出了基于标签传播和蚁群优化的AntLP算法（Hosseini和Rezvanian，2020）。Feng提出了一种鲸鱼优化算法EP-WOCD。该算法基于增强的鲸鱼种群行为，以克服数据大小对算法时间复杂度的影响（Feng例如， 2020年）。3. 预赛社区检测需要对图及其性质有基本的了解。本节描述了重要的术语，这些术语对于理解我们的社区检测新方法至关重要，如图所示。1 .一、图G=（V，E）是顶点V={v1，v2................................................ vn}的集合，边E= {e1，e2，en}。每个边都包含一个有序的con对，连接的顶点社交网络可以被视为现实世界中的图形，以人为节点，以他们的互动为边（Akhtar和Ahamad，2021）。一个社区可以简单地定义为图G的一个子图，它的簇内边比簇间边多（Lancichinetti and Quinato，2009）。例如，在社会网络中，一个社区将由一群人组成，他们之间的互动比其他人更多，如图所示。1.一、模块 化是计算 网络划分 为模块 的强度的 最流行 的度量之 一（Zhang和Chen，2018）。模块化得分高表明社区内部的连接较密集，社区外部的连接较稀疏模块范围从1到1。它被计算为落在组内的边与随机分布中的预期边的差。模块化由Newman引入（Newman，2006 a; Newman，2006 b）。其定义如等式中所示。（一）.2我这里eii表示网络中连接簇i中顶点的边的分数，ai表示随机网络中来自或去往组i的边。通常预期值范围为0.3至0.7。模块度优化是各种通信检测算法的基础图密度可以被定义为图中的边的数量与具有相同数量的节点的完整图中的边的数量的比率（Danisch等人，2017年）。一个图可以是稠密的或稀疏的，这取决于它的边的数量。Fig. 1. 社区在一个图。由图形成的社区可以称为不相交或重叠。一个不相交的社区是一个其中每个节点只属于一个社区 另一方面，在重叠社区中，节点可以同时属于多个社区（Xie等人， 2013年）。 在现实世界中，大多数社区是重叠的，因为一个人可以同时是许多社区的成员，如图所示。1 .一、节点的成员资格表示其对特定社区的归属性成员资格可以是清晰的或模糊的。一个清晰的成员只能有两个值，0和1.这意味着节点可以属于社区或不属于社区，分别用1和0表示。另一方面，模糊隶属度考虑了特定社区中重叠节点的相似性强度（Mahajan和Gupta，2021）。根据节点对特定社区的参与程度，模糊优先级的值范围从0到1，如图1所示。在图1中，蓝色节点只属于社区C1，因此它们的成员资格为C1 = 1和C2 = 0。同样，红色节点只属于社区C2，因此它们的成员资格对于C2 = 1，对于C1 = 0。另一方面，绿色节点是重叠节点，属于C1和C2。在社区C1中，它是三个3集团的成员，在社区C2中，它是两个3集团的成员因此，模糊隶属度可以计算为C1 = 3/5= 0.6和C2 = 2/5 = 0.4。一个社区由几个节点组成。每个节点在社区中的参与程度不同，这被称为影响力。最有影响力的节点是连接到组中大多数其他节点的节点，如图1所示。另一方面，影响力较小的节点将具有较少的连接节点（Peng等人，2018年）。影响分析对于获得更合理的社区检测结果至关重要。图的离群节点是那些不属于任何社区（Domingues等人，2018年）。这是因为他们较少参与社区的互动，这使他们处于社区之外，如图1所示。在图1中，黄色节点是离群节点。离群值检测有助于检测社区中的异常情况。团是图的完全子图（Luo，2018）。例如，5clique表示其中5个节点彼此连接的子图，如图2所示。1.一、4. 该方法在这一节中，我们将讨论我们提出的算法的问题陈述和详细描述。4.1. 问题陈述对任意图G=（V，E），其中Vv 1v 2v 3;vn是顶点的集合，并且E1/4 e1;e2;e3;-;ej是边的集合，所考虑的现有社区检测算法形成社区，使得如果Ci和Cj是所形成的任何两个社区，则对于所有i-j， 这表明两个社区不共享任何顶点，即只检测不相交的社区此外，离群节点，节点的模糊隶属度，节点的影响力也没有得到。4.2. 该算法在这一节中，我们提出了一种新的算法，该算法可以检测出具有模糊成员关系的重叠社区，离群节点和社区中最有影响力的节点。此外，该算法形成的社区D. Singh和R. Garg沙特国王大学学报7768¼ ðÞ具有比考虑中的现有算法形成的社区更好的模块化值‘‘NI-Louvain”首先，对所考虑的图进行预处理，以得到密度比前一个更小的处理后的图。然后将Louvain第三步，将社区图中的节点转换回原社区图中的节点，计算社区中的最有影响力节点、重叠节点、模糊隶属度和离群节点。NI-Louvain的伪代码在下面的算法中描述，整个过程的流程图如图2所示。每个阶段的详细信息在小节中描述。设G V;E是一个图，其中V是输入图的顶点集，E是输入图的边集。设G0V0;E0是另一个图，其中V 0fg和E0fg：从图G/V/E/V计算所有3个集团。将团标记为节点，V0¼V0[fsetofcliquenodesg：对于V中的如果团i和团j在E中有2条公共边.然后，E01/4E0[f，i，j，g]。得到处理后的图G0<$V0;E0<$。在图G0 上计 算鲁 汶多级 群落. 将V0分解得到其组分V.图二. NI-Louvain流程图计算每个V的成员。通过考虑多个成员身份来计算重叠节点。考虑每个社区中节点出现的次数，得到模糊隶属度、节点影响力和离群点。4.2.1. 步骤I：输入图的密度降低我们的新方法包括三个步骤。首先对图进行预处理，降低图的密度.4.2.1.1. 密度降低的动机。我们已经在6个真实世界的数据集上应用了Louvain的多级算法，即风筝，空手道，猕猴，美国机场，免疫和安然。我们计算了输入图的密度和在每种情况下获得的社区模块度。我们的实验表明，如果我们忽略微小的变化，在大多数情况下，模块化与图的密度成反比，如表1和图3所示。因此，如果我们能进一步降低图的密度，我们将得到更好的模值。4.2.1.2. 密度降低法。我们已经处理了所考虑的数据集，即图G，以降低密度，为此，我们使用团渗透方法计算了数据集节点的3个团。我们只计算了3个团，因为通过增加团的维度，数据集大小将增加，这无法通过我们的顺序方法处理创建团图的步骤如下：● 在输入图G中搜索大小为3的所有团。以前一步中得到的团为结点，生成新的图G0.如果两个节点（团）有2条公共边，则它们在新图中由边连接。通过计算3团，得到了一个改进的图G0. 我们比较了图G和图G0在不同数据集上的密度，发现图G0的密度小于图G的密度. 图G和G0的密度在图中进行了比较。 四、4.2.2. 步骤2：社区检测第二步，在G 0上应用Louvain的多层算法得到社区.4.2.2.1. 选择Louvain多级算法的动机。 Singh等人比较了由7种算法形成的社区的模块化，即边缘介数，标签传播，领先特征，Louvain，Fast Greedy，Walktrap和Infomap在6个真实世界的数据集上，即immuno，美国机场，空手道，猕猴，风筝和安然（Singh和Garg，2020）。表3显示了获得的模块化在每一种情况下都是如此。图5示出了比较的结果。很明显，Louvain算法提供了一致的性能和更好的表1通过Louvain算法得到数据集的密度和相应社区的模块度数据集密度用Louvain算法求社区的模块度免疫0.00720.83美国机场0.040.45空手道0.140.44猕猴0.230.38风筝0.40.22安然3.720.45●●D. Singh和R. Garg沙特国王大学学报7769.Σ≤123我图3.第三章。6个真实世界数据集的数据集密度与社区模块度之间的关系表2图G和G0 的 密 度.数据集图G的密度图G0的密度免疫0.00720.0006美国机场0.04120.0019空手道0.140.076猕猴0.230.019风筝0.40.19安然3.720.002图五.不同社区检测算法生成的社区模块度比较。步骤1：每个节点被分配到其邻居的社区。然后计算所有受影响节点的模块度。如果modularity的变化是积极的，我们保持在这个社区的节点。否则，节点将再次分配给其先前的社区。这是重复的，直到社区分配没有变化第二步：将第一步中形成的社区视为节点，这称为粗粒度网络。步骤3：重复步骤1和2，直到我们在后续步骤中得到相同的结果。现在我们得到一个社区，它比图G上计算的社区具有更高的模块度。4.2.3. 步骤3：将V0更改为V中的组成节点因为V0是由团作为节点组成的。现在计算V0中节点的成员资格当量（2）表示初始图G中的顶点集V¼ v1;v2;v3;-;vn2当量（3）表示图G0 中 团 节 点 的 集 合.V0¼。v0;v0;v0;-v03如果在实验之后获得j个社区，则成员资格集在等式中示出。（四）图四、 图G与G0 的 密 度 比 较。M¼. m1; 立方米-mj4模块化的价值比其他算法。因此，我们在我们的新方法中使用了Louvain算法。4.2.2.2. 从G0开始检测社区。本文将Louvain的 多 层 算 法 应 用 于G0. 算法步骤如下：给你。<现在，我们根据这些隶属度计算不同的参数。4.2.3.1. 重叠的节点。具有多个成员资格的节点称为重叠节点。如果有两个社区，表3通过不同算法形成的社区获得模块度值数据集节点边缘模块化边介数标签传播领先特征鲁汶快速贪婪步行陷阱InfoMap风筝10180.180.0970.170.220.220.120.097空手道34780.350.430.440.440.430.440.43猕猴454630.270.240.360.380.350.330.28安然184125,4090.330.140.350.450.260.550.19美国机场75523,4730.320.260.420.450.430.350.32免疫131663000.870.740.860.830.780.860.76D. Singh和R. Garg沙特国王大学学报7770CDCDCDCD和Cg，并且来自V 0的任何两个节点属于这些社区，如等式（1）所示。（5）Eq.（六）、v02Cf5v0 2Cg100g然后这两个节点的成员资格将如等式所示（7）Eq.（八）v0！mf200v0 ！mg8现在，如果V中的任何节点v k使得v ksv0 和v ksv0同时，5. 实验结果与讨论为了对新算法进行评价，我们在一些真实网络数据集上将其性能与传统的Louvain算法进行了比较。它们是：风筝，空手道，猕猴，美国机场，免疫和安然。表4描述了用于实验的硬件和软件的列表。5.1. 数据集我们已经在6个真实世界的数据集上评估了“NI-Louvain”的性能风筝，空手道，猕猴，美国机场，免疫和安然。我们没有使用比这些更大的数据集，C d因此，v k的成员资格将如等式（1）所示。（9）Eq. （十）、vk！ m f200v k！ mg10然后，v k是重叠节点，因为它具有多于一个社区的成员资格。4.2.3.2. 节点的影响。在社区内多次出现的节点此属性将增加节点的影响力。在我们的实验中，如果来自V0的两个节点属于相同的社区，如等式2所示。（十一）v0;v0sCf11然后，这两个节点将具有相同的成员资格值，如等式中所示（十二）v0;v0 ！男女12岁现在如果V中的任何节点vk使得v ksv0和v ksv0速降烷并行算法需要分析较大的数据集，但5.1.1. 风筝它通常被称为克拉克哈特风筝图。它是由社会网络理论研究者DavidKrackhartt在1990年提出的。它有10个顶点和18条边（Brandes和Hildenbrand，2014）。5.1.2. 空手道韦恩·W扎卡里在他的论文“小团体冲突和裂变的信息流模型”（Csardi和Csardi，2015）中介绍了扎卡里它由一个空手道俱乐部的社交网络组成。1970年至1972年进行了研究。它由34个成员（节点）组成。一场冲突导致俱乐部一分为二。它有78条边5.1.3. 猕猴它由猕猴的视触脑区和连接的图形模型组成。它由45个区域和463个定向连接组成（Csárdi等人， 2016年）。C d因此，它在社区Cf中将有2个成员。这将增加节点vk在社区yCf中的影响。 以这种方式，在社区内具有最高出现次数的节点将是该社区的最有影响力的节点。4.2.3.3. 节点的模糊隶属度。重叠的节点将同时属于多个社区。此外，对不同社区的归属感强度可能不同。通过计算重叠节点出现的次数来计算重叠节点的模糊隶属度。对于V中的任何节点v k，v k在任何社区中的模糊隶属度Cf将由Eq给出。（十三）、模糊隶属度5.1.4. 美国机场它是2010年12月在美国的航班网络。它是一个有向图，有多条边，显示美国不同机场之间的航班。它由755个顶点和23，473条边组成（Qiu等人， 2020年）。5.1.5. 免疫它是免疫球蛋白相互作用网络。它由1316个代表氨基酸的顶点和6300 条 边 组 成 如 果 两 个 氨 基 酸 之 间 的 最 短 距 离 小 于 阈 值 8Armstrong，则存在两个氨基酸之间的边缘（Csardi和Csardi，2015）。Kfvk在Cf中出现的次数vk在所有社区中的总发生次数ð13Þ5.1.6. 安然这是一个电子邮件数据集，由美国公开。离开-例如，如果v k同时属于两个社区，即 vk2Cf 和vk2Cg。 如果vk在Cf中的出现次数为x，v k在Cg中的出现次数为y，则v k在两个社区中的模糊隶属度由等式（1）给出。（14）Eq.（十五）、正义的力量它由184个节点和125，409条边组成（Csardi和Csardi，2015）。5.2. 结果F中vk的模糊隶属度vk在Cg中的模糊隶属度X1/4×100mmy1/4×100mmð14Þð15Þ由鲁汶和NI-鲁汶产生的所有群落的模块性比较结果如表5和图所示。六、表4实验中用到的硬件和软件4.2.3.4. 离群节点。离群节点是那些不属于任何社区的节点。在我们的实验中，通过计算不属于任何团体的节点来识别离群节点，即所D. Singh和R. Garg沙特国王大学学报7771有社区的成员资格为零。处理器Intel Xeon E-2124 G CPU，4 Cores内存8 GB编程语言Rx64 3.5.3操作系统LinuxD. Singh和R. Garg沙特国王大学学报7772从表5和图6中可以清楚地看出，NI-Louvain算法生成的社区比Louvain算法生成的社区具有更高的模块度值我们的实验表明，NI-Louvain提供了高达45%的模块化值相比，Louvain的算法的增量此外，我们还获得重叠节点，最有影响力的节点，模糊隶属度和离群值，这是由下面的例子说明。5.2.1. 示例图示我们在风筝数据集上展示了我们的实验结果风筝数据集的图表如图所示。7.第一次会议。当我们在风筝数据集上应用Louvain算法时，我们得到3个社区C1，C2，C3 ，如图8所示。如果我们在同一个风筝数据集上应用NI-Louvain算法，那么也会得到3个社区C1，C2和C3，如图所示。9.第九条。图 8、得到的社区是不相交的社区，离群节点、影响力节点没有被识别。另一方面，在图9中，属于社区的节点以维恩图的形式示出。节点的多次出现由具有相同标签的多个圆圈指示节点2、4、6和7是重叠的，因为它们属于多个社区。节点9、10不属于任何社区，因此它们是离群值。模糊隶属度可由公式Eq.（十三）、通过观察图9获得的不同参数示于表6、表7、表8和表9中。类似地，我们分别以表10和表11的形式示出了空手道和猕猴数据集类似的表可以很容易地获得其他数据集，但由于表的大小和空间的限制，我们只显示了三个数据集。5.3. 讨论通过观察结果，可以清楚地看出，NI-Louvain算法给出了比以前的算法更好的模块度值。表12显示了在考虑的6个数据集上通过不同算法形成的社区的模块度值。可以看出，在每种情况下，NI-Louvain的模块化值最高在表13中，我们比较了基于附加参数的不同算法，例如重叠节点，最有影响力的节点，节点的模糊成员资格，以及在社区检测期间获得的离群值。从表13中可以看出，只有NI-Louvain提供了关于社区的额外信息。这些值可用于电信网络中可疑事件的检测、推荐系统、链接预测、信息扩散、了解具有重叠社区结构的网络上的流行病传播。在图10中，我们已经示出了由Louvain和NI-Louvain算法针对三个较小的数据集（即，风筝、空手道和猕猴）生成的社区的凸包表示。我们只考虑了较小的数据集，以获得更清晰的社区视图，因为大型图的凸包表示不会产生节点和社区的清晰视图。表5由Louvain和NI-Louvain产生的模块化。鲁汶尼卢万风筝0.220.32空手道0.440.52猕猴0.380.51美国机场0.450.51免疫0.830.93安然0.450.57图六、Louvain和NI-Louvain生成的模块化比较见图7。风筝数据集的图形表示。见图8。在风筝数据集上应用Louvain算法后获得的社区。小图的凸壳表示是表示社区及其对应节点的有效方法。它可以帮助我们分析和比较不同算法产生的结果。从图10中可以看出，NI-Louvain将图划分为比Louvain算法更好定义的社区此外，NI-Louvain提供以下优势，正在考虑的算法模块性增加模块性增加表明更好的社区形成。它在流行病传播中有广泛的应用（Valdez et al.， 2020年）。●D. Singh和R. Garg沙特国王大学学报7773图9.第九条。在Kite数据集上应用NI-Louvain后获得的社区表6每个社区中节点出现的频率和模糊隶属度。所属节点群集频率模糊隶属度表10由NI-Louvain在空手道数据集上形成的社区以及每个社区的组成节点和模糊隶属度。社区成员（模糊隶属度值）小区11（0.22）、5（1.0）、6（1.0）、7（1.0）、11（1.0）、17（1.0）小区225（1.0）、26（1.0）、32（0.33）小区33（0.09）、9（0.8）、15（1.0）、16（1.0）、19（1.0）、21（1.0）、23（1.0）、24(1.0)、27（1.0）、28（1.0）、29（1.0）、30（1.0）、31（1.0）、32（0.67）、33(1.0)、34（1.0）小区41（0.78）、2（1.0）、3（0.91）、4（1.0）、8（1.0）、9（0.2）、13（1.0）、14(1.0)、第十八条（1.0）、第二十条（1.0）、第二十二条（1.0）异常值10,12表11NI_Louvain在猕猴数据集上形成的社区以及每个社区的组成节点和模糊隶属度。1241.000（0.03）、25（0.28）、29（0.46）2210.250小区39（0.03）、10（0.08）、12（0.01）、14（0.04）、16（0.19）、17（0.17）、182330.750（0.01）、19（0.09）、20（0.03）、25（0.11）、29（0.11）、30（0.23）、393231.000（0.03）、45（0.25）4110.125小区43（0.07）、5（0.52）、7（0.6）、8（0.14）、10（0.09）、13（0.16）、164240.500（0.09）、17（0.22）、18（0.2）、19（0.82）、20（0.88）、21（1）、22（1）、4330.37523（1）、24（1）、25（0.61）、26（1）、27（1）、28（1）、29（0.04）、305331.000（0.46）、35（0.03）、44（0.5）、45（0.5）6120.400社区51（1）、2（0.5）、3（0.45）、4（0.97）、5（0.48）、6（0.26）、7（0.4）、86230.600（0.36）、9（0.43）、10（0.1）、11（0.19）、12（0.38）、13（0.11）、147120.400（0.96）、16（0.26）、17（0.02）、18（0.17）、29（0.1）、30（0.02）7330.600小区63（0.1）、4（0.03）、8（0.12）、9（0.11）、10（0.16）、11（0.16）、128111.000（0.13）、13（0.63）、15（0.14）、16（0.19）、17（0.17）、18（0.12）、20（0.06）、29（0.15）、30（0.1）、35（0.03）、40（0.08）、41（0.1）小区713（0.1）、15（0.4）、17（0.2）、29（0.02）、30（0.13）、31（1）、32（1）、33（1）、34（1）、35（0.94）、36（1）、37（1）、38（1）、39（0.93）、40（0.89）、41（0.86）、42（1）、43（1）、44（0.5）、45（0.25）表7每个社区最有影响力的节点群集最具影响力的节点频率16，7221，44三、二、四、五、七三表8重叠节点。重叠节点集群22,341,2,361,271,3表9离群节点。异常值9，10重叠节点和节点的模糊隶属度重叠节点同时属于多个社区，因此它被广泛用于推荐系统（Zhang等人，2018年）。根据任何节点的模糊隶属度值，可以从一个社区向另一个社区推荐各种事物。社区模糊隶属度（Fuzzy Membership）小区12（0.12）、3（0.1）、8（0.11）、9（0.11）、10（0.13）、11（0.14）、12（0.12）、15（0.46）、17（0.11）、18（0.1）、29（0.13）、30（0.07）、39小区2（0.03）、40（0.03）、41（0.05）2（0.38）、3（0.28）、6（0.74）、8（0.27）、9（0.32）、（0.51）、12（0.35）、16（0.28）、17（0.11）、18（0.4）、19（0.09）、20●D. Singh和R. Garg沙特国王大学学报7774离群值无节点的影响用于信息传播和社交推荐系统（Xiong et al.， 2019年）的报告。离群节点离群节点的检测形成社交媒体中的欺诈检测和异常检测的基础（SURI等人， 2019年）的报告。6. 今后工作在这个实验中，我们只考虑了3个集团，因为我们的实验主要是顺序的。我们已经观察到，当我们进一步增加团的维数时，我们得到图的密度进一步降低，如表14所示。但是通过增加团维数，数据集的节点和边的数量也会增加，从而增加数据大小。所以它不在序列算法的范围内在未来的工作中，我们将在并行环境中实现该算法，以考虑所有可能的问题，并得到更好的结果。7. 结论‘‘NI-Louvain”该算法通过对数据集进行预处理来降低图的密度，●●D. Singh和R. Garg沙特国王大学学报7775表12通过不同算法在6个数据集上获得的社区模块度值。数据集节点边缘模块化边介数标签传播领先特征鲁汶快速贪婪步行陷阱InfoMap尼卢万风筝10180.180.0970.170.220.220.120.0970.32空手道34780.350.430.440.440.430.440.430.52猕猴454630.270.240.360.380.350.330.280.51安然184125,4090.330.140.350.450.260.550.190.57美国机场75523,4730.320.260.420.450.430.350.320.51免疫131663000.870.740.860.830.780.860.760.93表13基于不同参数的不同社区检测算法的比较因素算法边介数标签传播领先特征鲁汶快速贪婪步行陷阱InfoMap尼卢万重叠社区检测没有没有没有没有没有没有没有是的模糊隶属没有没有没有没有没有没有没有是的节点影响计算没有没有没有没有没有没有没有是的离群点检测没有没有没有没有没有没有没有是的见图10。用NI-Louvain算法和Louvain算法构造社区的凸包表示。表14团维数对图数据集密度的影响集团数据集345678910密度空手道0.520.1500猕猴0.510.530.530.50.380英国教师0.540.590.610.640.640.620.490安然0.570.620.620.670.680.680.640.65反过来又增加了生成社区的模块化在预处理中，我们根据节点的影响力得到社区中不同频率的节点。节点的影响力是社区检测的一个重要因素，可以更好地了解社区中发生的事件及其预期结果。我们的方法有很多优点。通过应用该方法，重叠的节点被识别，每个节点的模糊隶属度值，离群点和社区的最有影响力的节点被识别。正因为如此，我们得到了更详细的知识对社区结构进行了改进，提高了生成社区的模块性。我们只考虑了模块化，但还有其他因素，如执行时间，调整rand索引，拆分连接距离等，对社区检测算法进行了评价，并将其应用于今后的社区检测工作中。此外，我们还将尝试修改我们的顺序算法，一个并行平台，可以处理三个以上的团图并进行大数据分析。D. Singh和R. Garg沙特国王大学学报7776竞争利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作。引用北阿赫塔尔，Ahamad，M.V.，2021.在：研究选集数字化转型，组织变革，以及远程工 作 的 影 响 。 IGI Global ， pp. 485-500. https://doi.org/10.4018/978-1-7998-7297-9.ch025网站。Blondel，V.D.，纪尧姆，J.L.，兰比奥特河，Lefebvre，E.，2008.在大型网络中快速展开社区。 J. St a t . Mech：Theory Exp. 2008（10），P10008.Brandes，Ulrik，Hildenbrand ，Jan，2014. 具有不同单点中心的最小图。NetworkScience 2（3），416-418.布兰德斯大学，Delling，D.，Gaertler，M.，格尔克河Hoefer，M.，Nikoloski，Z
我的内容管理
展开
