快速重叠社区搜索

lecea

        论文标题：FOCS: Fast Overlapped Community Search
        论文作者：Sanghamitra Bandyopadhyay, Garisha Chowdhary, Debarka Sengupta

        本文的贡献在于提出了快速重叠社区搜索算法（FOCS），一种通过计算局部连通性来识别重叠社区的算法。该算法考虑节点的局部信息，快速、高效而且能够克服内存限制。
       

前提知识

        社区检测：是识别自然存在的社区，使得社区内的节点彼此连接得很密集，同时不同社区的节点之间连接比较稀疏。

        社交网络：可以概括为有限数量的“个体”和“个体之间的连接”，连接通常基于他们的共同兴趣，由于兴趣的多样性和动态性就会导致形成一些重叠的结构，在这种情况下，要分割成不相交的集群是不适用的，而且形成的网络规模通常很大。

        连通性的定义
        令N(vj)为节点vj∈V的邻居节点的集合：N(vj)={vk|(vj,vk)∈E}
        令Ni(vj)为节点vj,对于社区Si∈S(vj)的社区邻域:Ni(vj)={vk|(vj,vk)∈E∩Vk∈Si}
        社区连通性(community connectedness)：对于节点vj相对于社区Si，其在内的社区邻域的大小与社区的大小减1的比率，即

（社区连通性得分决定了节点对其社区的归属性）
        为了确保任何社区中的节点在社区内至少具有K个邻居，改进定义的社区连通性为：

        如果K非常大，小而密集的社区就会被错过；如果K非常小，就会发现更稀疏的大社区和不重要的小社区。对于低的K值，该算法是不敏感的，一般来说K = 2是社区检测的合理选择。
        邻域连通性(neighbourhood connectedness)：对于节点vj相对于社区Si，其在内的社区邻域的大小与其（整体）邻域的大小的比率，即

（邻域连通性得分仅定义了加入新社区的节点的兴趣）
        下表是基于社区连通性得分和领域连通性得分在其社区中的节点的状态。

        截止分数的选择
        对于每个节点vj∈V的，范围为0到1，把整个范围被划分为max(20,N(vj))个相等大小的桶，每个桶初始值设置为0，当列表中的得分落在其范围内时，桶的值增加。完成后，标记值大于0的最右侧的桶，从那个位置开始向左扫描桶列表，直到找到一个≤标记桶的值且其左侧的桶的值≧当前的桶的值的桶，若到最左边还未找到，则标记最左边的桶。对于顶点vj，将该值设置为保留截止分数(stay cut-off)，采用这种方法有助于选择接近最佳连接的社区。
        对于每个节点vj∈V的，可以用类似的方法定义加入截断分数(join cut-off) 。
        一个用到的结论

（意思就是每个节点的平均社区数取常数值，与网络的大小无关）

        原有社区检测算法的缺陷
        第一，已知“社区之间的重叠区域比社区的非重叠区域更密集”，而大多数现有算法是假定“社区比其周围区域更紧密”，就错误地把社区的重叠部分识别为了社区。
        第二，许多算法有计算时间要求，大多数发现的是不相交的社区，找到重叠社区所需的计算量很大，算法在计算时间上有限制，这使得它们不适用于大规模的真实网络。
        第三，有些需要将社区的数量作为输入，但是在大多数情况下社区数量并不可知。

正文

        为了解决原有算法在重叠社区检测中遇到的困难，本文作者提出FOCS算法，它是一种快速算法，在局部连通性的基础上演化来发现重叠的社区，能够在大型社交网络上扩展。它还通过同时选择多个最接近的社区来提高速度，有助于保存多个迭代。通过该方法检测到的社区不限于特定层级，包括给定网络中的所有有意义的社区。此外，该方法是确定的，即结果不依赖于节点输入的顺序。
        原理
        社区的初始化是每个节点与他的邻接节点建立社区，当一个节点发现自己没有足够的连接时，这个节点会离开某些它所在的社区，并受邻居和邻居社区的影响，如果找到足够的连接就可能会选择留下，吸引其邻居成为其社区的一部分。形成的新社区继续迭代，使得社区进一步扩展。在迭代的过程中很有可能会形成重复的社区，所以增加了一个重复社区删除的过程，这样可以使计算时间减少，从而提高了速度。
        问题定义
        对于一个无向无权图G(V,E),找到一个子图S={Si|Si⊂V}，使得对于子图Si中的任何节点vj在子图Si中比在另一子图S’j中有更多的连接，其中S’j=(vj∉Sk∩Sk∈S)是不包含节点vj的S集合中的任何子图，则子图Si∈S表示一个社区。
对于每个节点vj，∀j∈{1,2,...,|V|},令S(vj)={Si|vj∈Si∩Si∈S}是包含节点vj的社区的集合，S’(vj)=S-S(vj)是不包含节点vj的社区的集合。如果对于每个节点vj，只包含在一个社区里，即|S(vj)|=1，或者根本不是社区，即|S(vj)|≤1，称为不相交聚类，否则为重叠聚类。FOCS算法探讨在给定的重叠图中进行社区检测。
        过程
        1.初始化社区（Initial Communities）
        最初，每个节点vi,∀i∈{1,2,... |V|}，至少有K个邻居，与邻居建立社区Si。因此，社区的数目等于度数大于K的节点数。
        初始社区结构表示为S0，Si的外围节点的集合定义为。初始化后进行迭代，每次迭代称为一个阶段(stage)，一个stage又分为两个phase：离开阶段(leave phase)和扩展阶段(expand phase)。将在某个stage l之后获得的社区结构表示为Sl。注意，对于任何社区，Sl中的节点始终是外围节点，在以后的阶段离开或扩展。
        2.离开阶段（Leave Phase）
        在这个阶段，当一个节点发现自己没有足够的连接时，这个节点会离开某些它所在的社区。
        对于每个节点vi，都分别有社区连接性(community connectedness)和邻居连接性( neighborhood connectedness)两个得分，所以对于社区结构S1中的每个节点vj，可以得到社区连通性得分列表和邻域连通性得分列表。如果节点具有大于某个截止分数的社区连通性得分，则认为该节点在其社区中充分连接。现在对于所有的社区Si∈Sl，如果低于，则外围节点vj∈Addedi从Si移除。仅移除外围节点确保了形成社区核心的节点不会被消除，而且剩余的度数小于K的节点也要被消除。递归地对整个社区结构执行计算得分和外围节点的移除，直到没有节点离开。
        3.扩展阶段（Expand Phase）
        在离开阶段之后，开始将社区扩展到其相邻节点。对于每个社区Si，如果以下条件成立，把每个相邻节点vj包括进外围节点集Addedi中：
        该节点还没有在这个社区里；
        该节点非常有兴趣加入这个社区。
        当一个节点的大于，表示有很有兴趣加入社区。Addedi设置为包含新添加节点的Si（或如果没有添加新节点则为空集），在下一阶段进行leave或expand。一方面，仅扩展外围节点允许重新包含移除的节点，另一方面不适合社区的节点不被重复地添加，并且稍后在leave phase被移除。它有助于FOCS 收敛。在expand phase之后，在此stage获得的社区结构作为输入被传递到下一stage的leave phase。当在某一个stage，所有现有社区中没有剩余外围节点时，FOCS停止。
        4.重复删除（Duplication Removal）
        重叠社区检测算法允许网络中的节点可以是多个社区的一部分，这是因为每个社区在扩展时不管该节点在其他社区中是否存在都允许被包括进来。因此，某些可能成长为接近重复的社区。这种接近重复的社区对(C,C’)通过相似性度量来识别，值越大越相似，等于1表示重复社区完全相同。
        在FOCS中重复删除，以参数OVL作为输入。OVL设置两个社区之间允许的最大重叠的阈值，当相似性度量大于OVL时，将其识别为“近似重复”，删除两个社区Si和Sj中的较小者。
        下图为Dolphin network进行FOCS过程的图示。

        算法

        时间复杂度分析
        对于给定的无向图，未加权图G(V,E)，令n=|V|是节点的数量，m=|E|是边的数量，l是每个节点的平均社区数。则FOCS在各个阶段的时间复杂度分别为：
        社区初始化：O(m)；
        离开阶段：O(nl2+n+nl)=O(nl2)；
        扩展阶段：O(nl3)；
        删除重复：O(nl3)。
        所以，FOCS总的时间复杂度为O(m+nl2+nl3+nl3)=O(m+nl3)=O(m+n)≈O(m)(根据前面提到的Theorem A.1.可知，l取常数值，与网络的大小无关，所以时间复杂度可以表示为O(m+n)，又因为m＞n，所以可以表示为O(m))。下图为FOCS与其他算法时间复杂度的比较。

        实验结果
        可以在真实网络和仿真网络上评估社区检测算法的性能。但是，模拟网络没有捕获与真实网络中的社区结构相关的一些重要特性，所以本文只评估FOCS在真实网络上的性能。用归一化互信息（NMI）进行性能评估，在大规模的7个无向和未加权的真实网络上进行评估。
        这七个网络为：Amazon、DBLP、YouTube、LiveJournal、Orkut、Yeast PPIN、Human PPIN，下表提供了具体细节。

        下表报告了各种算法在这七种网络上所花费的执行时间。

        下表总结了检测到的和地面实况社区之间的NMI。

        下图显示了随着边缘数目m的增加，FOCS与其他七个现有算法相比的运行时间。

        可以看出，在给定的时间和内存约束下，除FOCS之外的任何算法都不能很好地扩展到较大的社交网络数据集。
        FOCS还需解决的问题
        1)通过FOCS检测的社区的最大数量等于网络中的节点数，而在社交网络中，社区的数量事实上可以比节点数量多，在我以后的研究中可以考虑解决这个问题。
        2)FOCS只适用于无向无权图，希望可以扩展该方法，使其使用到加权网络、定向网络、动态网络等。
        3)从各个算法时间复杂度的比较图可以看出，时间性能比较好的是SLPA和FOCS，都是O(m)，而在上一篇得到过一个结论：对于低重叠密度网络，SLPA、OSLOM、Game和COPRA提供比其他测试算法更好的性能；对于高重叠密度网络，SLPA和Game提供更好的性能。所以可以比较SLPA和FOCS，找到各自的优点，然后再某方面结合起来，可能会有更好的性能。

总结

        社交网络复杂而庞大。快速重叠社区搜索(FOCS)通过计算局部连通性来快速探索重叠社区。在整个算法中为每个节点计算的社区连通性和邻域连通性得分反映真实社区属性，使得算法适用于不同大小的真实网络，用户可以自由地设置任何两个社区之间的最大允许重叠以及节点的最小邻居数，以确定其在某一社区中的成员资格。但是该算法应用在实际网络中仍有需要改进的地方。

        论文链接：