RAK算法非常容易描述。 每个顶点都与一个标签相关联，标签是标识符，如整数。
1 .初始化时，每个顶点都有唯一的标签
2 .然后，重复一遍，每个顶点x更新其标签，并将其替换为最多邻居使用的标签。 如果要对同一最大邻居数使用多个标签，请随机选择其中一个。 重复几次后，相同的标签倾向于与社区中的所有成员相关联。
3 .具有相同标签的所有顶点添加到一个社区中
传播阶段在连续迭代中并非所有顶点都收敛到具有相同标签的状态。 为了确保传播阶段结束，Raghavan等人建议使用“异步”更新。 即，顶点标签根据一部分邻居的以前的标签和另一部分邻居的更新标签进行更新。 节点按随机顺序排列。 在第t次迭代中，x的新标签基于第t次迭代中x的上一个邻居的标签和(t - 1 )次迭代中x的下一个邻居的标签。
算法结束后，每个顶点都有标签，是最大数量邻居使用的标签之一。
该算法生成包含共享相同标签的所有顶点的组。 组中的每个顶点对之间有一个路径，该路径只通过同一组中的顶点，因此这些组不一定相连。 由于社区通常要求相互连接，Raghavan等人提出了最后一个阶段，将这些组分为一个或多个相互连接的社区。
重叠社区
在RAK算法中，顶点标签标识顶点所属的各个社区。 如果社区重叠，则每个顶点可能属于多个社区。 因此，很明显，为了找到重复的社区，必须允许顶点标签包含多个社区标识符。
每个顶点x可以用一对(c，b )标记。 其中c是社区标识符，b是归属系数，表示社区c中x成员的强度。 因此，x的所有归属系数的总和为1。
每个传播步骤将x的标签设置为邻居标签的和，并且社区通过合计所有邻居归属系数来标准化。
更准确地说，函数bt(c，x )将顶点x和团体标识符c映射到迭代t中的归属系数，
这里n(x )表示x的近邻集合。 (计算所有邻居节点属于c社区的隶属度与邻居节点数的比) ) ) ) ) ) ) ) ) ) ) )。
在我们的算法中，迭代t的一个顶点的标签总是基于迭代t1的相邻标签。
您需要的是在每个标签上保留多个社区标识符，而不是保留所有标识符。 我们的方法利用归属系数在实现该目的的：传播的每个步骤中，首先构建上面描述的顶点标记，然后移除归属系数的对。 将该阈值表示为倒数、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，然后重新对齐{(a，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
较小的社区，但不受网络大小的影响。更新：COPRA算法的标签传播与隶属度归一化 由图可知节点 1 对 a、b、c、d 社区的从属系数分别为 1/4、7/24、5/24、1/4， a = (1/3+2/3)/4 = 1/4 b = (1/2+2/3)/4 = 7/24 c = (1/2+1/3)/4 = 5/24 d = (1/2+1/2)/4 = 1/4 假设此时的 v 设置为 2，那么结点1需要选取隶属度排序前 2 的社区并归一化： 先对a，b, c, d社区的隶属度进行排序（b = 7/24 ，a = 6/24 ，d=6/24，c = 5/24），会选择a，b或b，d 归一化： a，b：a = （6/24）/ （6/24+7/24）= 6/13 ； b = （7/24）/ （6/24+7/24）= 7/13 同理b, d : b = 7/13 ； d =6/13 ，这时会随机选择一组最为结点1的标签