基于聚类系数的社团检测算法研究
发布时间：2021-07-12 02:09
复杂网络种类繁多,遍及人类社会的方方面面,涉及到的学科领域也复杂多样,复杂网络研究工作吸引了相关领域研究人员的关注,也越来越受重视。特别是二十一世纪以来,互联网技术取得了前所未有的跨越式发展,对复杂网络研究工作具有很大的推进作用。近年来,来自相关领域的专家学者提出了很多复杂网络进行社团检测算法,标签传播算法就是其中比较经典的一个,该算法具有高效快速、无需先验信息等优点,但也存在稳定性不足、容易形成巨型社区等缺点。本文对已有的复杂网络社团检测算法做了较为细致的研究,尤其对标签传播算法的具体步骤和优缺点进行了认真研究,并对网络的聚类系数性质进行深入分析,由节点的聚类系数和网络的聚类系数,扩展提出了社团聚类系数的概念。针对标签传播算法存在的结果不稳定、容易形成巨片社区等问题,本文结合点聚类系数和社团聚类系数的概念,分别提出了基于点聚类系数的标签传播改进算法和基于社团聚类系数的标签传播改进算法。其中,基于点聚类系数的标签传播改进算法首先根据节点的聚类系数和度对节点进行优先级排序,在初始化标签阶段改进策略,仅对优先级较高的节点进行标签初始化,在标签传播过程中根据节点的聚类系数对邻节点进行排序,选...
【文章来源】：兰州大学甘肃省 211工程院校 985工程院校 教育部直属院校
【文章页数】：62 页
【学位级别】：硕士
【部分图文】：
无权无向图
兰州大学硕士学位论文基于聚类系数的社团检测算法研究122.2.3聚类系数节点的聚类系数是节点的重要属性，通俗来讲，它描述节点的邻居节点之间互连的概率。除了节点的聚类系数，还有边的聚类系数、网络的聚类系数以及社团的聚类系数，为避免歧义，一般会加上限定词，比如称点聚类系数或称为某节点的聚类系数。假设节点的度为，即节点有个邻居节点，如果该节点的邻居节点之间也都两两互连，那么，这些邻居节点之间就存在(1)/2条边。这时，节点和它的邻居节点就构成一个完全图。然而实际情况中，节点的邻居节点之间不一定全部互相连接，所以邻居节点之间实际存在的边数是小于等于(1)/2的。点聚类系数的计算公式为：=((1))/2=2(1)(2-3)，上式中，代表节点的个邻居节点之间实际存在的边数。当=0或=1时，必有=0，此时上式的分母也为0，我们记=0。那么，的范围就是[0,1]。节点聚类系数的定义也可以从网络中三角形的数量方面来阐述。等价于以节点为顶点之一的三角形的个数，而根据节点有个邻居节点，所以以节点为顶点的三角形至多有(1)/2个。而以节点为中心的连通三元组的数目，就等于以节点为顶点的三角形的最大可能数目。因此，从几何上给出节点的聚类系数如下：=包含节点的三角形的数目以节点为中心的连通三元组的数目(2-4)图2-2以节点i为中心的连通三元组的两种可能形式公式（2-3）和公式（2-4）给出了节点的点聚类系数的两种定义，网络的聚类系数的定义因此也有两种。网络聚类系数的第一种定义为根据公式（2-3）推广，即求出该网络所有节点的点聚类系数的均值，公式如下：=1∑=1(2-5)
兰州大学硕士学位论文基于聚类系数的社团检测算法研究22（3）根据增量矩阵每一行的最大增量，求出增量最大堆。（4）根据增量最大堆，求出其中的最大增量。（5）根据最大增量对应的两个节点，合并他们的社团，并更新增量矩阵、最大堆和最大增量。（6）重复步骤（4）和（5），直到网络所有节点都划分到一个社团。由以上算法步骤可知，在CNM算法的计算过程中，模块度只有一个最大值，所以取模块度取最大值时对应的社团划分结果作为网络的社团结构。CNM算法的计算过程采用了最大堆来计算模块度增量，算法时间复杂度为(2)。2.6.4BGLL算法BGLL算法是Blondel等人[17]提出的一种基于模块度优化的社团检测算法，该算法能够用于检测加权网络。由于提出该算法时，作者均在鲁汶大学就职，因此该算法又名Louvain算法。该算法步骤如下：（1）首先，遍历所有节点，根据节点间的连接情况和网络的总结点数等属性，依次计算节点之间的模块度增量，构成一个模块度增量矩阵，再由矩阵得到其中最大的模块度增量，若该增量为正，则将当前节点加入该邻居节点所在社团，若为负，保持节点的社团不变。重复上述步骤直到合并现象不再发生，就得到第一个阶段的结果。图2-3BGLL算法的处理过程（取自文献[17]）（2）其次，根据（1）的结果，把社团作为节点，将原社团之间存在的边数作为新节点之间的权重，重新构建一个新的网络，然后对新网络执行（1）的步骤。直到整个网络划分为一个社团或不能再划分为止。图2-3显示了BGLL算法对包含16个节点的网络的社团检测的处理过程：第一层结果包含4个社团，第二层包含2个社团。
【参考文献】：
期刊论文
[1]一种面向社区发现的高鲁棒性标签传播算法[J]. 郑少强,赵中英,冯慧子,李超. 小型微型计算机系统. 2018(08)
[2]基于加权聚类集成的标签传播算法[J]. 张美琴,白亮,王俊斌. 智能系统学报. 2018(06)
[3]基于矢量影响力聚类系数的高效有向网络社团划分算法[J]. 邓小龙,翟佳羽,尹栾玉. 电子与信息学报. 2017(09)
[4]基于模块度优化的标签传播社区发现算法[J]. 李磊,倪林. 计算机系统应用. 2016(09)
[5]基于标签传播概率的重叠社区发现算法[J]. 刘世超,朱福喜,甘琳. 计算机学报. 2016(04)
[6]标签传播算法理论及其应用研究综述[J]. 张俊丽,常艳丽,师文. 计算机应用研究. 2013(01)
[7]一种基于聚集系数的局部社团划分算法[J]. 李孔文,顾庆,张尧,陈道蓄. 计算机科学. 2010(07)
[8]复杂网络研究概述[J]. 周涛,柏文洁,汪秉宏,刘之景,严钢. 物理. 2005(01)
本文编号：3278976
【文章来源】：兰州大学甘肃省 211工程院校 985工程院校 教育部直属院校
【文章页数】：62 页
【学位级别】：硕士
【部分图文】：
无权无向图
兰州大学硕士学位论文基于聚类系数的社团检测算法研究122.2.3聚类系数节点的聚类系数是节点的重要属性，通俗来讲，它描述节点的邻居节点之间互连的概率。除了节点的聚类系数，还有边的聚类系数、网络的聚类系数以及社团的聚类系数，为避免歧义，一般会加上限定词，比如称点聚类系数或称为某节点的聚类系数。假设节点的度为，即节点有个邻居节点，如果该节点的邻居节点之间也都两两互连，那么，这些邻居节点之间就存在(1)/2条边。这时，节点和它的邻居节点就构成一个完全图。然而实际情况中，节点的邻居节点之间不一定全部互相连接，所以邻居节点之间实际存在的边数是小于等于(1)/2的。点聚类系数的计算公式为：=((1))/2=2(1)(2-3)，上式中，代表节点的个邻居节点之间实际存在的边数。当=0或=1时，必有=0，此时上式的分母也为0，我们记=0。那么，的范围就是[0,1]。节点聚类系数的定义也可以从网络中三角形的数量方面来阐述。等价于以节点为顶点之一的三角形的个数，而根据节点有个邻居节点，所以以节点为顶点的三角形至多有(1)/2个。而以节点为中心的连通三元组的数目，就等于以节点为顶点的三角形的最大可能数目。因此，从几何上给出节点的聚类系数如下：=包含节点的三角形的数目以节点为中心的连通三元组的数目(2-4)图2-2以节点i为中心的连通三元组的两种可能形式公式（2-3）和公式（2-4）给出了节点的点聚类系数的两种定义，网络的聚类系数的定义因此也有两种。网络聚类系数的第一种定义为根据公式（2-3）推广，即求出该网络所有节点的点聚类系数的均值，公式如下：=1∑=1(2-5)
兰州大学硕士学位论文基于聚类系数的社团检测算法研究22（3）根据增量矩阵每一行的最大增量，求出增量最大堆。（4）根据增量最大堆，求出其中的最大增量。（5）根据最大增量对应的两个节点，合并他们的社团，并更新增量矩阵、最大堆和最大增量。（6）重复步骤（4）和（5），直到网络所有节点都划分到一个社团。由以上算法步骤可知，在CNM算法的计算过程中，模块度只有一个最大值，所以取模块度取最大值时对应的社团划分结果作为网络的社团结构。CNM算法的计算过程采用了最大堆来计算模块度增量，算法时间复杂度为(2)。2.6.4BGLL算法BGLL算法是Blondel等人[17]提出的一种基于模块度优化的社团检测算法，该算法能够用于检测加权网络。由于提出该算法时，作者均在鲁汶大学就职，因此该算法又名Louvain算法。该算法步骤如下：（1）首先，遍历所有节点，根据节点间的连接情况和网络的总结点数等属性，依次计算节点之间的模块度增量，构成一个模块度增量矩阵，再由矩阵得到其中最大的模块度增量，若该增量为正，则将当前节点加入该邻居节点所在社团，若为负，保持节点的社团不变。重复上述步骤直到合并现象不再发生，就得到第一个阶段的结果。图2-3BGLL算法的处理过程（取自文献[17]）（2）其次，根据（1）的结果，把社团作为节点，将原社团之间存在的边数作为新节点之间的权重，重新构建一个新的网络，然后对新网络执行（1）的步骤。直到整个网络划分为一个社团或不能再划分为止。图2-3显示了BGLL算法对包含16个节点的网络的社团检测的处理过程：第一层结果包含4个社团，第二层包含2个社团。
【参考文献】：
期刊论文
[1]一种面向社区发现的高鲁棒性标签传播算法[J]. 郑少强,赵中英,冯慧子,李超. 小型微型计算机系统. 2018(08)
[2]基于加权聚类集成的标签传播算法[J]. 张美琴,白亮,王俊斌. 智能系统学报. 2018(06)
[3]基于矢量影响力聚类系数的高效有向网络社团划分算法[J]. 邓小龙,翟佳羽,尹栾玉. 电子与信息学报. 2017(09)
[4]基于模块度优化的标签传播社区发现算法[J]. 李磊,倪林. 计算机系统应用. 2016(09)
[5]基于标签传播概率的重叠社区发现算法[J]. 刘世超,朱福喜,甘琳. 计算机学报. 2016(04)
[6]标签传播算法理论及其应用研究综述[J]. 张俊丽,常艳丽,师文. 计算机应用研究. 2013(01)
[7]一种基于聚集系数的局部社团划分算法[J]. 李孔文,顾庆,张尧,陈道蓄. 计算机科学. 2010(07)
[8]复杂网络研究概述[J]. 周涛,柏文洁,汪秉宏,刘之景,严钢. 物理. 2005(01)
本文编号：3278976
本文链接：https://www.wllwen.com/shoufeilunwen/benkebiyelunwen/3278976.html
