链接：社群发现(中)
qxde01发表于 2013-02-04 22:25:46
社会网络分析中的分层划分（Hierarchical Clustering，层次聚类）中的分裂法的做法是找出相互关联最弱的节点并删除它们之间的边，通过这样的反复操作将网络划分为越来越小的组件，也可以在任何时刻终止这个过程并将当时的结果作为社区结构，同样也可以用系统树描述这个将网络划分为越来越小的团队的过程。Grivan-Newman(GN)算法有些类似，GN算法是基于edge betweenness的算法。
边介(edge betweenness)被Newman定义为通过该边的节点之间的最短路径的条数，并且不同社区之间的边的介数(betweenness,betweenness centrality的简称??)值较高。该方法是通过不断地寻找并删除 边介值最高的边来得到社会网络中的社区结构的，称此算法为 GN 算法，其步骤为：
- Step1：计算网络中每条边的 betweenness;
- Step2：删除 betweenness 值最高的边；
- Step3：重新计算所有边的 betweenness;
- Step4：重复 Step2- Step4 直到所有的边都被删除。
可以将 GN 算法看作是一种分裂法，不过与一般分裂法不同的是，GN 算法不是寻找关联最弱的节点对然后删除它们之间的边，而是寻找最“between”的边并删除它。通常一条边的删除会很大程度上影响到许多其它边的 betweenness 的值，因此，每次在执行完边的删除之后，必需重新计算所有边的 betweenness 值。这是一个非常耗时的任务，为此，Brandes和Newman分别给出了一种快速重新计算边介的方法。
该方法的基本思想是：选择一个节点作为中心节点(Center)，只考虑中心节点和其它节点之间的最短路径，计算每条边由当前这些最短路径得到的 betweenness 值，并将计算结果添加到当前该边的 betweenness 和中。然后，改变中心节点，即选择另外一个节点作为中心节点，并重复刚才的计算过程直到每个节点都曾被选中作为中心节点为止。因为在刚才的计算过程中，每条最短路径的端点都被计算过两次，计算得到的每条边的 betweenness 的和正好等于该边准确的 betweenness 的两倍。
在R:package:igraph的基于边介的Grivan-Newman社群发现算法实现函数为edge.betweenness.community(……)。在我的人人网好友关系中，可以很好地发现两大密集的社群，其余的比较散乱地分布在周围。
- 标签传播算法
标签传播(label propagation)算法是一种近线性算法，其复杂度只有O(km)，k为迭代次数，通常情况下k<
在R:package:igraph的近线性的标签传播社群发现算法实现函数为label.propagation.community(……)，该函数使用节点的权重作为限制条件，其初始化参数initial可以设定节点的标签。在我的人人网好友关系中，在没有限定任何条件下，只能发现两大社群，对于小型社群无法识别。
