社区发现算法-团渗透

简介

    k-团渗透算法(CPM)[1]是第一个能够发现重叠社区的算法，重叠社区指的是结点可以同时属于多个社区。重叠社区在社交网络中是十分常见的，因为每个人都有着多种多样的社交关系。

算法

    网络中的最大团指的是，团中任意两个结点之间都有边连接，并且它不被其他的团所包含。CPM算法的想法非常简单，首先它找出网络中所有大小至少为k的最大团。然后构建一个团图，每个最大团都是团图中的一个结点，如果两个团c1与c2共享min(c1,c2)-1个邻居的话，它们在新图中的结点之间就存在边。最后团图中的每个连通单元就是一个结点的社区，而它可能是重叠的。
代码参见

并行化

挖掘最大团的过程可以改造为map reduce格式的，详细过程请见[3]

代码参见

参考文献

1: Uncovering the overlapping community structure of complex networks in nature and society
2: The worst-case time complexity for generating all maximal cliques
and computational experiments
3: Efficient Dense Structure Mining using MapReduce