图2.1 网络社区 避风塘奶茶店校园市场调查问卷表
在这种情况下，Palla等人提出了一种系派过滤法（CP算法）来分析这种相互重叠的社团结构。
Palla等人认为，一个模块从某种意义上可以看成是一些相互连通的“小的全部耦合网络”的集合。这些“全耦合网络”称为“派系”。K-派系表示该全耦合网络的节点数目是K。如果两个K-派系有K-1个公共节点，则称这两个派系相邻。如果一个K-派系通过若干个相邻的K-派系去到了另一个K-派系，则称这两个K-派系是连通的。K-派系社团是由所有彼此连通的K-派系构成的集合。
下面我们来举个例子：2-派系代表了网络中的边，2-派系社团即表示网络中的连通的子图。3-派系代表网络中的三角形，3-派系社团代表彼此连通的三角形的集合。在该社团中，任意相邻的两个三角形都具有一条公共边。
在CP算法中，采用由大到小，迭代归回的算法来寻找网络中的派系。寻找网络中的派系如下：
①从网络中各节点的度可以判断网络中可能存在的最大全耦合网络的大小s。
②从网络中一个节点出发，找到包含该节点的大小为s的派系后，删除该节点及连接它的边（避免多次找到同一个派系）。（这一步是算法的关键步骤）
③另选一个节点，重复步骤2，直到网络中没有节点为止。（此时找到了网络中所有大小为s 的派系）
④s=s-1,返回步骤2。
在上面的步骤中，最关键的一步是如何从一个节点v出发，寻找包含它的所有大小为s的派系，对这个问题，CP算法采用了迭代算法：
首先，对于节点v定义两个集合A和B。A为包括节点v在内的两两相连的所有点的集合；B为与A中所有节点都相连的节点的结合。为了避免重复选择到某个节点，在算法中，在集合A和B中的节点的序号顺序排列。
在定义A和B后，算法如下：
①初始集合A={v}，B={v的邻居}
②从B中移动一个节点到集合A，同时调整集合B，删除B中不再与A中所有节点都相连的节点。
③如果A大小未达到s前集合B已为空集，返回，继续寻找新的派系。否则，当A达到s，就得到一个新的派系，记录此派系， 继续寻找新的派系。
由此就可以得到从v出发的所有大小为s的派系。
然后我们来说下利用派系寻找K-派系社团。
什么是重叠矩阵：矩阵的每一行（列）对应一个派系。对角线上的元素表示相应派系的大小（派系中的节点数目），非对角线上的元素代表两个派系之间的公共节点数。
将重叠矩阵中对角线元素小于k的置为0，非对角线元素小于k-1的置为0，其他元素置为1，此时，得到一个k-派系社团结构的连接矩阵（该矩阵表明了大小大于k的社团之间的连接情况）。
注：不同的k值会影响到最终得到的社团结构，而且，随着k值得增大，社团会越来越小，但是结构会越来越紧凑。但是，网络的社团结构仅取决于系统本身的特性，与k的取值没有太大关系。
上一页 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 下一页