文摘

大数据的爆炸性发展,信息数据挖掘技术也在迅速发展,而复杂的网络已成为数据挖掘的一个热门研究方向。在现实生活中,许多复杂系统将使用网络节点智能检测。当使用许多社区检测算法时,出现很多问题,所以他们不得不面对的改进。新的检测算法CS-Cluster提出派生通过使用不同的节点附近。当然,本文提出的新算法是基于IGC-CSM算法。做出一定的改进,和CS-Cluster IGC-CSM四个算法的实现,SA-Cluster W-Cluster, S-Cluster。比较的结果上的密度值熵值的政治博客的数据集,DBLP数据集,政治博客数据集和DBLP数据集的熵值。最后,得出CS-Cluster算法是最好的聚类的效果和质量,和程度的不同子图的聚类结构。

1。介绍

复杂系统在社会生活和自然可以智能地检测到网络节点。当生活的社区算法可以解决许多问题,它已广泛应用,同时也促进了复杂网络社区探测系统的改进。网络模块指导的一项研究发现,其价值将渗透和改变1),和定向网络模块重叠,重叠中心包括两个方面,出入口。揭示了在社区结构是复杂网络研究的关键问题(2];即形成的节点组模块和社区将形成一个单位,但单位之间的联系很薄弱。目前的研究发现,网络连接分区允许社区重叠在节点(3),和连接分区的算法可以生成多个节点分区通过重叠和折线图显示异质性程度的作用。与网络动力学相结合,一种新的社区检测算法(4),通过两个原则来解释新算法,用于检测强劲的重叠社区。此外,研究人员分析了现实社会基于重叠网络结构的研究(5),然后提出一种新颖的检测整个社区总体框架。根据研究,发现SLPA具有良好的性能在识别节点和不同程度的重叠社区。提出了一种算法,是非常实用的,可以发现重叠社区在一个巨大的网络(6]。一样的传统算法的顶点有标签相同的顶点之间传播。本文的主要贡献是扩大标签和传播步骤,该算法是非常有效的恢复。研究人员发现,有必要验证信息识别现实世界大规模网络的社区结构(7];在更换的过程中,紧密连接节点形成一个共识,一个独特的标签,并生成一个社区。目前,研究人员使用新的社区检测算法研究中删除high-different无关的节点分裂过程中的子组(8]。提供一个通用框架的实现方法,该方法的应用计算机网络和不同的现实世界的网络显示了该方法的有效性。构建块的识别是非常重要的,对于理解网络结构和功能特征9]。使用新技术来发现重叠社区规模大,并定义新特性通过社区统计数据。基于拓扑特征研究[10SCP),研究人员提出了一种新的渗透算法,在选择执行社区快速检测模块的加权和未加权的网络。识别网络使用越来越多的(11),它导致了缺乏功能重叠社区的共识,所以前面的算法扫描修改相应的解决一些属性的缺陷。此外,研究人员发现一种完全可以解决的社会网络模型(12),提供了简单的一党和党网络模型并比较模型的预测结果与社交网络在现实世界中。隐藏的关系揭示了复杂网络(13),但此时检测方法不稳定,结果受很多因素的影响。在自洽的情况下结合任何方法,分区结果的稳定性和准确性大大提高。研究提出了一种简单直观的网络凝聚力的方法(14],它可以在几行代码来实现。根据研究,节点可以实现分离很明显影响最好的图和聚类方法的质量和效率。网络社区结构算法提出了人口划分的连接子组(15]。经过一系列的计算,证明该方法也有很大的影响在现实世界中网络数据研究基于上述复杂网络社区探测算法智能。

越来越成熟的数据挖掘技术(16],复杂网络在各个领域的广泛应用,集群技术了。分析复杂网络中的社区结构不仅可以使研究人员更深入地理解节点在复杂网络的结构和性能特征,但也有助于发现复杂网络的演化规则。

2。基本的社区检测算法

如今,随着大数据爆炸的时代,数据挖掘技术取得了快速的进步,复杂网络已经成为数据挖掘领域的一个热门研究方向。提出了一个社区检测方法(17];这是一个层次聚类方法。它使用随机游走模型来计算网络中的不同节点完成分工网络。Radicchi等人使用edge-based聚类系数的概念来完成社区结构的识别(18];该方法首先计算边缘的聚类系数,选择低附加值的边缘,然后逐步删除它们识别社区。该算法的优点是,它可以成功地应用于大型网络。一个社区检测算法(GN算法)是在2002年提出19,20.];该算法是一种算法基于分裂的想法。它最初计算边缘的中间状态值包含在网络和不断更新的中间性价值网络中剩余的边缘,直到所有网络中的边删除,从而获得社区结构。一个网络社区检测算法提出了基于最小生成树和模块化(21];它意识到社区通过分层检测的想法。此外,检测算法,识别社区提出了基于标签的想法传播(22];这个算法首先定义一个标签中的所有节点图,然后按顺序替换节点的标签我与最邻近节点所拥有的标签。和一个新的算法存在的边的数量最小化外部网络社区划分图(23最后完成社区的认可,但该算法必须提前知道社区的数目。此外,开发层次聚类算法(24];根据信息中心的规则,这种方法使用信息中心来检测边缘社区,逐步消除边缘图中价值最高的信息中心来确定社区结构。检测算法,NMF算法,还提出(25),它使用拉普拉斯算子矩阵的重叠的一个给定的网络,实现社区的认可。

在本章中,我们引入了节点dissimilarity-node接近的程度。在不同的基础上,提出了一个新的聚类算法,CS-Cluster,。该算法综合考虑了节点的拓扑结构和语义信息比较完整的聚类过程效率高。与其他算法相比,该算法具有以下特点:(1)利用节点的结构和语义特征来计算节点的距离;(2)根据不同的节点,连接模式的贡献程度和匹配度,分别添加到参与计算的结构不同;(3)该算法可以自动确定初始聚类中心点,从而提高了聚类的准确性,减少人类主观判断造成的错误,因为不同的初始聚类中心的选择将产生更大的影响最终的聚类结果。

在网络图在这一章,探讨语义类型中包含节点的数量是恒定的,这是不可能的语义类型的数量是不一致的。一个无向加权图可以表示与语义信息 ,代表 图中的所有节点的集合;E表示图中的所有连接的边的集合。每条边的边集E网络的两个节点对应的节点集V图 ,也就是说, ,无向图中边的权重集,节点的连接边的权重和节点代表的一组节点的语义信息(属性) 图中;设置节点的值在语义信息可以表示为 。的节点总数直接连接到节点称为该节点的程度 。

图聚类算法的目的是把一个大型图表分成几个密切相关和不相交的子图(即。在以下)、社区通过聚类过程,应满足以下:(1)同一社区的内部节点在结构上面的紧密相连,和对象不同社区之间的连接相对稀疏;(2)节点的语义特征在同一社区是相似的,但在不同的社区,节点的语义信息是不同的。

3所示。社区测试算法的计算和替换

3.1。计算节点的距离

3.1.1。相关性和匹配

本文提出一种基于节点的邻近社区检测算法。节点之间的亲密关系取决于节点之间的相关性。它显示了节点之间信息传递的特点。相互连接的节点,可能有多个初始节点和目标节点之间的路径。IGC-CSM算法和考虑加权连接边的选择(26]。参与路径最小的重量的计算结构不同,而不是所有路径参与计算,减少了计算量。在本章提出的算法介绍了关联度和匹配度的基础上IGC-CSM算法完成的计算结构不同。

定义1。(程度的协会)。在无向网络图权重,一双直接连接节点和 。连接亲密的程度定义为协会的程度。然后,计算公式节点之间的关联程度和节点是 如下: 这定义 之间的相关系数节点 。它表明节点相关联的程度的节点 : 表示节点的程度 ,和代表连接节点的边的权重和节点 。它代表的权重的总和 ,所有的边连接到节点 ;因为度节点的不同,各自的连接边缘上的重量是不一样的,所以呢 。例如,在DBLP网络,作者可能与许多作者有关。这些作者其他作者与他们相关联,因此这些作者的相关系数是不同的。更大的价值 ,两个节点之间的关联程度越高,和两个节点之间的关系。假设有两个直接连接的节点和 , 和的意思是分别为和; , 代表节点和节点 ,连接上的重量。然后,吸引因素和的总和 计算如下:

定义2。(匹配路径)。一双间接连接节点 ,从源节点通过一些中间节点终点,路径传递被称为匹配路径 ,和路径上的所有节点通过只有一次。 代表作为初始节点,代表结束节点, 代表了两个直接相连的节点之间的相关系数。无向加权网络图,可能会有多个匹配路径的路径从初始节点到终点 。我们选择的道路与高度匹配的最佳路径从初始节点到终点 。

3.1.2。结构不同

计算方法之间的邻接节点映射节点之间的关系。组成的无向加权网络图节点的结构特点和语义信息,所以在计算节点的距离,应该是由节点的结构特点和语义特征。,并添加相关的概念和匹配计算过程的结构不同。我们决定使用Jaccard相关系数来计算的基本结构不同。公式如下:

IGC-CSM算法使用加权Jaccard相关系数计算。由于节点之间的连接方法的差异,相应的结构不同IGC-CSM算法的计算方法也不同。具体计算公式如下:(1)当两个节点是直接连接 ,表达的计算方法 (2)对两个间接连接节点的总和和 ,IGC-CSM算法计算产品的形式直接连接节点的序列。具体计算方法如下: 和其特点检查方法: 其中,( )代表一条直接连接节点。因为有多条路径过程从最初的节点到目标节点 ,IGC-CSM选择最低的路径体重和不考虑所有路径计算,大大简化了计算量增加,提高计算的效率。其中,在网络边缘的总数,和节点的度和分别和分别为节点和社区;如果 ,然后 ,值为0。在一个特定的网络结构,社会分工的结果是不一样的,所以获得的模块化值也不同;如果模块化较大,算法分区比较大。(3)当两个节点相对独立,结构不同是0。

之后介绍了相关性和匹配的概念,不同的结构和语义不同的图中的节点可以计算。计算方法是基于IGC-CSM算法添加节点的关联度和匹配度。的计算结构不同可分为三种情况根据节点的连接模式:(1)两个直接连接的节点,完成不同计算结合加权Jaccard相关系数和节点之间的相关性。(2)两个间接连接节点,结构不同和节点之间的匹配程度IGC-CSM算法用于完成的计算结构不同。在节点之间的路径和间接连接,可能会有更多的匹配路径;我们选择的道路与高度匹配的初始节点和终端之间的最佳路径参与计算。(3)无关联的节点(独立节点),结构不同的IGC-CSM算法是0。计算公式如下:

其中,意味着结构的程度不同,⟶意味着两个节点直接连接,Θ意味着源节点和是间接连接到终点,这意味着该节点没有连接边缘,属于一个独立的节点。

间接节点的结构相似度计算是通过产品实现的路径上的节点序列,以及计算方法

其中, 两个点是序列对意义和直接连接。可能有多条路径从源节点到节点,但IGC-CSM使用加权最短路径策略,以避免大量的计算过程。

图聚类的过程中根据不同的节点,如果节点之间的结构特点,划分的结果可能不准确,因为,在现实生活中,一个节点可能携带多个语义信息。例如,在一个社交网络,用户可以执行不同的角色在不同的地方。此外,它还可能包括属性,如职业和爱好。因此,当我们比较节点不同,我们还应该考虑他们的语义不同。一个节点包含多个语义信息,每个语义可能需要不同的值。我们使用的方法计算不同K-Modes算法中节点之间的语义相似度。为方便计算,我们设置了语义重量为1。

表1显示在复杂网络structure.where符号的意义代表的是语义的程度不同,是语义重量;表示数量的语义;当语义值是相同的,该值为1;当语义值是不同的,该值为0;因此语义值范围是[0.1]。

3.1.3。节点的距离

节点之间相似度的计算应综合考虑节点的结构特点和节点之间的语义特征,所以我们把邻近的节点来完成计算节点之间的不同。这个公式所示(13):

其中,是平衡的因素,旨在调整的比例在不同的计算结构和语义。它的值范围是[0,1];表示结构不同;代表了语义不同。在以后的实验的一部分,这一章将给最合适的值 。

当价值大,它将更有可能成为集群中心;noncluster中心过渡到集群中心时,该值将进行更改,所以我们定义一个转移函数表明,跳发现聚类中心点的具体计算公式的过程如下:

从公式可以看出,价值就越大 ,更大的节点的值的变化 ;然后,该节点应该成为初始聚类中心,所以按降序排序结果,最大的关键价值被认为是初始聚类中心的观点。

计算节点距离后,我们使用节点距离完成聚类过程。自邻近的距离成反比,也就是说,距离越大,节点之间的关系越近,和对应的距离值越小,所以我们用距离来计算距离的倒数。计算公式如下:

根据本章的算法框架实现聚类,计算公式如下: 代表秩序的邻接矩阵。当时,代表节点属于第一subcommunity;当时,这意味着该节点不属于社区。它代表一个群集中心集合点。

集群的选择中心点应该满足以下两个条件:(一)的局部密度中心点应该足够大(B)不同的中心subassociations彼此相距较远

对于节点的局部密度的定义,计算公式可以表示为

其中,是截止距离,它的值,其他节点距离的平均值。 代表除了其他节点 。从定义可以看出,节点的数量就越大节点的距离越小,值越大吗 。

3.2。算法的迭代更新

迭代更新CS-Cluster算法的步骤如下,其中 , ,分别代表了集群中心点和邻接矩阵在第一个更新。(1)这一点与最大的前一个值计算公式(8)作为初始聚类中心的观点 ,邻接矩阵是计算 根据公式(9)(2)当不会改变,计算并获得最小值 根据公式(12);如果它是 ,该算法迭代结束;否则,执行步骤(3)(3)当不会改变,计算并获得 ,根据公式(最小值9)。如果它是 ,该算法更新结束;否则,继续步骤(2)

当不会改变,更新方法如公式所示(9),范围值 和值范围 。

当没有改变,更新方法年代如下:

在算法的执行过程中,集群中心点将每次迭代后更新,最后剩下的节点将被分为最近的类别与更高的密度从每个集群中心。

聚类算法的伪代码CS-Cluster提到在本章算法所示1:

平衡的因素 。摘要不同的平衡因子值应用于数据集观察平衡的影响因素和熵密度。当平衡系数是0.6,有更高的密度值和更低的熵值。参见4.3获取详细信息。

4所示。实验验证

在这个实验中,五个算法作为比较算法,即IGC-CSM, SA-Cluster, W-Cluster S-Cluster, CS-Cluster。其中,IGC-CSM、SA-Cluster W-Cluster三个集群中的算法。节点的拓扑结构和节点的语义信息是全面考虑在课堂上的过程。IGC-CSM算法使用K-Medoids框架来实现聚类,和SA-Cluster使用随机游走技术。迭代过程非常耗时。W-Cluster算法通过加权函数用于计算不同节点之间的程度。S-Cluster算法也使用随机游走的技术,但该算法只考虑节点的结构特点。CS-Cluster算法是在本章提出的算法。相关的概念并给出匹配算法完成计算图中的节点之间的结构不同和集成节点的结构不同;语义的程度不同计算节点的距离,重新定义的选择初始聚类中心点,最后实现社区的划分。

4.1。数据集

本章使用了两个经典的数据集来验证该算法的有效性。(1)政治博客数据集:这个数据集是由不同的博客之间的联系。为每个博客中包含的数据集,有一个语义描述政治方向,自由党的0和1的保守党成员。政治方向上的数据来自博客目录。(2)DBLP数据集:我们使用的一个sub-data-sets-author协作网络;我们创建了一个图,反映了作者之间的合作关系。此外,我们添加了两个阶段包括在每个节点网络图。

相关的语义信息:信息反映评价指标的数量和主题的论文。有三个可选的论文数量的值,小于10,10至20岁和大于或等于20日确定作者是“多产。”另一个语义是主题。对于主题的属性,我们获得了论文标题所选的作者和组织这些论文标题为文档。最后,我们提取的研究主题文件,包含100种可能的值是随机分配代表每个主题的关键词。每个作者的主题属性将对应于这些100年主题表2。

4.2。评价指标

比较算法用基于密度的聚类结果进行了评估和熵,所以本章还使用密度和熵来衡量聚类的效果。(1)密度:它被定义为边的总和的比例在子网整个网络的边缘。密度越高,和社区的聚类,聚类的分割效果越好社区,和公式如下: 在哪里 代表连接边的集合中的所有节点图,和代表总数的边缘。(2)熵:它是一个测量节点之间的语义相似度,当节点之间的语义相似度是一个类别。值越高,子网中的熵值越小,和更好的社会分工的结果。它的定义公式所示(19)和(20.): 其中, 和 代表的语义,代表了语义重量;代表节点的语义值的比例分割子图;和代表语义值的数量 。

4.3。实验结果

图1政治博客数据集。我们展示的密度值的比较结果5算法当集群的数量是3,5,7,9,分别。CS-Cluster变化缓慢的密度值随着数量的增加集群和一直高于其他四个的值比较算法。当Z= 7,其密度值是最高的0.93,表明CS-Cluster达到结构中不同节点在同一集群中的子图划分和是最好的。在五个算法,W-Cluster的密度值是最低的五种算法中,表明结构不同的节点在同一子图是最差的。随着集群的数量增加,密度值IGC-CSM仍基本持平,密度值相对较高,所以IGC-CSM的集群效应是仅次于CS-Cluster。

在图2,我们显示的密度值的比较五DBLP数据集的算法。在集群的数量继续增加,密度值W-Cluster算法的变化更明显,并与其他四个比较算法相比,其密度值达到最小值。因此,使用W-Cluster算法获得的检测结果。结构不同的节点在同一子图是最严重的;IGC-CSM和CS-Cluster有大致相同的密度值Z= 50,和密度值都高于0.85;但集群的数量高于50的密度值CS-Cluster略高于IGC-CSM;SA-Cluster的密度值是在中间的算法;从大局,CS-Cluster算法的平均密度高于其他四个的值算法,这表明,与其他算法比较,相比CS-Cluster有最好的结构不同的子图中的节点的聚类结果。

在图3,我们显示的熵值5的比较算法用于政治博客数据集。集群在实验中设置的数量z= 3,5,7,9。从实验图,我们可以看到的熵值CS-Cluster算法总是0;随着集群的数量继续增加,IGC-CSM的熵值几乎稳定在0.1左右,不变,所以它可以解释IGC-CSM和CS-Cluster的两种算法。它可以准确地分类语义相似的节点到相同的类别;但从密度值的对比图3的平均密度,就可以得出结论,CS-Cluster略高于IGC-CSM算法,所以CS-clustering集群算法具有优先于IGC-CSM质量。当z值从3增加到7日SA-Cluster的熵值基本保持不变,和价值仍然约为0.1,但当z值增加到9点钟,SA-Cluster突然的熵值增加,表明当集群的数量设置为9,语义不同的节点在同一子网很差。在所有的比较算法,S-Cluster算法熵值最高,表明获得的聚类划分的子图S-Cluster算法有最糟糕的语义不同节点之间。

图4是熵的四个算法的比较结果DBLP数据集。我们设置集群的数量z= 10、30、50、70。在W-Cluster五比较算法,算法具有最低的熵和平均价值维持在0.3;这意味着,在聚类结果,语义不同的子图中的节点非常高,但在图2,我们可以看到W-Cluster的密度值也相对较低。因此,它可以判断结构不同节点之间差;也就是说,节点之间的连接相对比较遥远。IGC-CSM的熵算法是最高的。随着集群的数量增加,CS-Cluster算法的熵值显示一个下降的趋势。当集群的数量高于30日SA-Cluster和CS-Cluster相比,聚类结果,语义不同节点之间是相对较高的,分类结果的准确性相对较高。

数据5和6显示平衡的影响因素λ密度和熵在政治博客数据集簇的数量z是15。从图可以看出5的增加x,整个密度逐渐增加的趋势,降低,然后增加。密度值的范围内λ从0.5到0.6几乎是不变的。从图可以看出6过程中熵值缓慢减少的价值从0.5到0.6,所以的价值λ0.6是更合适的。

5。结论

本文首先总结了传统社区聚类算法和相信之间的结构特点和语义信息节点聚类过程中应该考虑全面。在此基础上,本文提出了节点接近完整的计算节点之间的不同,介绍了协会的度和匹配度的概念,并完成结构的计算节点之间的不同。之后,选择初始聚类中心点的方法是重新定义。这种方法避免了缺陷引起的人类的判断,提高了聚类的准确性。最后,CS-Cluster算法使用K-Medoids框架实现社区部门。在其他的算法思想,实验比较两个实用和有效的数据表明,本文提出的算法取得了良好的聚类效果。数据挖掘和复杂网络社区探测是一个非常有意义的研究课题。本文进行相关研究的特点,网络中的节点和复杂网络社区探测。然而,仍有许多需要改进的问题。基于节点邻近社区检测算法,本文只研究无向加权网络图和忽略了集群中的节点网络图。 Secondly, how to effectively select semantic categories in the case of different semantic weight values is also not discussed in this study, which can be further discussed in the future.

数据可用性

使用的实验数据来支持本研究的发现可以从相应的作者。

的利益冲突

作者宣称,关于这项工作他们没有利益冲突。