资源-公共数据整理2014

社区标准数据集

• 1.GN网络

它是又plant l-分割模型[1]产生的。这个模型将图分解为l个社区，每个社区包含g个顶点，即n=gl，其中同一个社区内的顶点以概率p_in相连，而不同社区内的顶点以概率p_out相连。于是每一个子图对应的社区就变成了一个随即图，顶点之间以概率p_in相连。那么顶点的平均度为，<k>=p_in (g-1)+p_out (l-1)，当p_in>p_out时，说明社区内部边的密度要比社区间边的密度大，从而社区具有较明显的社区结构。

• 2.LFR网络

根据GN网络的生成方式，每个社区相当于一个随即图，每个顶点的度相同，每个社区的大小相等。然而这两个性质与真实的网络的要求并不一致。真实的网络的分布往往是倾斜的，大多数顶点的度是较小的，很多顶点的度是比较高的。对于社区大小分布来说，真实的网络的社区大小的分布也有类似的异质性。因此plant l-分割模型并不能很好地描述真实网络的社区结构，但是可以改进plant l-分割模型以能够描述度分布和社区大小分布。

• 3.空手道俱乐部网络

空手道俱乐部网络是一个著名的用于检验社区发现算法的标准网络。该网络包括34个顶点代表美国这个空手俱乐部的成员，这些成员被跟踪调查了两年多。成员之间的边表示在被观察到他们在俱乐部外面的联系，突然教练与主席之间的矛盾使得这个俱乐部分成了两个社区。

• 4.海豚网

是由Lasseaudu[2]对居住在新西兰的海豚分析得到的。该网络有62个顶点表示海豚数量。如果海豚经常被看见在一起而不是偶然的出现在一起，则认为他们之间存在一条边。突然一只海豚的离开使得网络分成了两个社区，这两个社区很容易被识别，两个之间仅有6条边。由于海豚网络的自然分割，像空手道俱乐部一样，也经常被用于检验社区发现算法的标准网络

• 5.美国大学足球队网络

另一个比较有名的网络是由Girvan和Newman[3]发现的美国大学足球队网络，该网络有115个顶点代表球队，如果两个球队之间有比赛，则产生一条边。球队被分成12个组，在同一组的两个球队要比不同组的球队的比赛的可能性大，因此就产生了一个自然地分组对应着比赛的分组。 除了上面所说的常用真实网络外，很多文章中还会用到合作网、蛋白质网、政治情感网络等。

References:

[1] Condon A, Karp R M. Algorithms for graph partitioning on the planted partition model[J].Random Structures and Algorithms, 2001, 18(2): 116-140.[2] D. Lusseau, The emergent properties of a dolphin social network, Proc. R. Soc. London B 270 (2003) S186-S188.[3] M. Girvan, M.E.J. Newman, Community structure in social and biological networks, Proc. Natl.Acad. Sci. USA 99 (12) (2002) 7821-7826.