HTML框架 JAVA学习 matlotlib VBA 分布式服务 sqlite d3 redux jwt postman vue图表 传智播客python 纯html网页模板 db2从入门到精通 java 数据分析 mysql转字符串 webform开发教程 axure导出html文件 python逻辑运算符 python集合 python输出 python安装教程 python中的map函数 python中的循环 python正则替换 java学习文档 java的instanceof java获取当前ip java判断 linux系统教程 选择模拟位置信息应用 模拟人生2夜生活 ip地址转换器 go程序设计语言 cad乘号 pp安卓助手 驱动程序更新 lol修改皮肤 mysql索引面试题 bat下载
当前位置: 首页 > 学习教程  > 编程语言

COPRA算法学习笔记

2020/12/5 10:34:14 文章标签:

RAK算法可以非常简单地描述。每个顶点都与一个标签相关联,标签是一个标识符,比如整数。 1.初始化时,每个顶点都有一个唯一的标签 2. 然后,重复地,每个顶点x更新它的标签,用最多邻居使用的标签替换它。如果…

RAK算法可以非常简单地描述。每个顶点都与一个标签相关联,标签是一个标识符,比如整数。

1.初始化时,每个顶点都有一个唯一的标签

2. 然后,重复地,每个顶点x更新它的标签,用最多邻居使用的标签替换它。如果相同最大邻居数量使用多个标签,则随机选择其中一个。经过几次迭代后,相同的标签趋向于与社区的所有成员相关联。

3.所有具有相同标签的顶点被添加到一个社区中

传播阶段并不总是收敛到这样一种状态,即在连续迭代中所有顶点具有相同的标号。为了确保传播阶段终止,Raghavan等人提出使用“异步”更新,即顶点标签根据一些邻居的先前标签和其他邻居的更新标签进行更新。节点被放置在一个随机的顺序中。在第t次迭代中,x的新标号是基于第t次迭代中x之前的邻居的标号和在第(t - 1)次迭代中x之后的邻居的标号。

算法终止时,每个顶点都有一个标签,是那些被最大数量的邻居使用的标签之一。

该算法生成包含共享相同标签的所有顶点的组。这些组不一定是连通的,因为组中的每一对顶点之间都有一条路径,该路径只通过同一组中的顶点。由于社区通常被要求是相互连接的,Raghavan等人提出了最后的阶段,将这些团体分成一个或多个相互连接的社区。

 

重叠社区

在RAK算法中,顶点标签标识顶点所属的单个社区。如果社区重叠,每个顶点可能属于一个以上的社区。因此,为了找到重叠的社区,我们显然需要允许顶点标签包含多个社区标识符。

我们可以用一组对(c,b)标记每个顶点x,其中c是社区标识符,b是归属系数,表示x在社区c中的成员强度,这样x的所有归属系数总和为1。

每个传播步骤都将x的标签设置为其邻居标签的并,将社区对所有邻居的归属系数求和并进行归一化。

更准确地说,假设函数bt(c,x)将顶点x和社区标识符c映射到迭代t中的归属系数,

其中N(x)表示x的邻域集合。(计算所有邻居结点属于C社区的隶属度和与邻居结点个数的比值)

在我们的算法中,迭代t中一个顶点的标签总是基于迭代t−1中它相邻的标签。

 

所需要的是一种在每个标签中保留多个社区标识符而不保留所有标识符的方法。我们的方法使用归属系数来达到这个目的:在传播的每个步骤中,我们首先构造如上所述的顶点标签,然后删除归属系数小于某一阈值的对。我们将这个阈值表示为倒数,1/v,其中v是算法的参数。因为每个标签中的归属系数和为1,v表示任意顶点可以属于的最大群体数。

一个顶点标号中的所有对的归属系数都有可能小于阈值。如果是这样,我们只保留拥有最大归属系数的一对,并删除所有其他的。如果超过一对有相同的最大归属系数,低于阈值,我们保留一个随机选择的其中之一。这种随机选择使算法具有不确定性。

在从顶点标签中删除对之后,我们将其重新正规化,方法是将每个剩余对的归属系数乘以一个常数,使它们的和为1。

 

 

使用这种方法,在v = 2的情况下,对上述网络的结果如图2所示。在第一次迭代中,顶点c被标记为社区标识符b和d,各归属系数为1/2。因为它不小于阈值(1/2),所以两者都保留。类似地,f被标记为e和g。其他五个顶点都至少有三个邻居,因此它们的归属系数都低于阈值。例如,先将b标为{(a,1/3), (c,1/3), (d,1/3)}:随机选择c,删除a和d,重新规整为{(c,1)}。a、d、e和g的标签同样是随机选择的。在最后一次迭代之前,a有两个邻居标记为c和两个标记为e,因此它保留了两个社区标识符:{(c,1/2), (e,1/2)}。因此,最终的解决方案包含两个重叠的社区:{a,b,c,d}和{a,e,f,g}。

 

 

 

 

我们的算法是RAK算法的一般化。如果v < 2,它们本质上是相同的:一个顶点的标签只能包含一个社区标识符,每个传播步骤保留最大数量的邻居使用的标识符。

算法思想:

与RAK算法一样,COPRA可能具有高度的不确定性,一个顶点的社区通常是由随机选择决定的。然而,在真实的网络中,COPRA通常比其他测试算法产生更好的结果(就模块化而言)。最近的工作表明,网络通常有大量的高模块化解决方案,没有明确的全局最大值,而且这些解决方案之间可能存在根本的差异,因此,这并不令人惊讶。也就是说,即使COPRA(或任何其他算法)每次运行时都找到不同的解决方案,这些解决方案也可能都是好的。

在我们的合成网络实验中,当混合或重叠相对较少时,结果是优秀且稳定的。然而,当混合或重叠增加过多时,一个不正确的随机选择可能导致社区标识符传播过多并淹没网络,性能突然下降。在这方面,LFM算法的表现与COPRA相似,而其他算法(CFinder和CONGO)往往会给出更差的结果,但随着混合或重叠的增加,结果会逐渐恶化。

COPRA在较大的网络中表现更好,在较小的社区中表现稍好。相比之下,CFinder倾向于较小的社区,但不受网络大小的影响。

 

 

 

 


本文链接: http://www.dtmao.cc/news_show_450272.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?