05-网络中的社区结构

社区网络

什么是社区

社区可以理解为一个一个由密切相连的节点聚集而成的团体，社区内部连接紧密，社区之间稀疏连接。

有一个很有趣的现象，通过调查研究发现，人们在找工作时，往往可以通过一般的熟人（acquaintances），而不是好朋友（close friends)获取更多的信息，弱连接（一般熟人）或许是我们认识多元世界的一个很重要的渠道，对于强连接（好朋友），往往因为足够了解，可以获得的额外信息并不多。

如下图所示，可以看作是三个社区，社区内部是强连接，社区之间弱连接。

image-20210305103623205

三角闭合

• 三角闭合 ==高度聚类系数

例子：如果B和C有一个共同的朋友A，则：

• B与C认识的可能性：因为他们都花时间和A在一起

• B和C之间互相信任：因为他们有一个共同的朋友

• A有激励b和c结合在一起的动机：因为A很难维持两种互不相干的关系

image-20210305103450151

边缘重叠

用边重叠指标可以定量地给边定义强弱。

$$O_{ij} = \frac{|N(i)\cap N(j)\setminus \{i,j\} |}{|N(i)\cup N(j)\setminus \{i,j\} |}$$

其中，$N(i)$是节点$i$的所有邻居，$O_{ij}$表示两个节点的邻居的重合程度，取值范围是$[0,1]$。

image-20210305104455368

如果$O_{ij}=0$，则节点$i$和$j$之间的边可以叫做局部桥，是一种很弱的连接，而$O_{ij}=1$，则这个边是强连接。它两端点的所有邻居都是重叠的。

边重叠是对网络结构的一种度量，它可以帮助解释Granovetter的理论。那么这种度量是否具有实际的意义？Jure在课程里使用了欧洲人通话网络的例子验证了，在实际的网络里，具有高边重叠的边，确实是有着强连接关系的。这里的强连接关系是采用的两个人之间的电话通话单位时间内的次数来衡量的。

模块度Q

模块度Q：一种衡量网络被划分为社区的程度的指标

给定网络划分成不相交的群$s\in S$：

$$Q \varpropto \sum\limits_{s\in S}[(\#\ edges\ within\ group\ s) - \underbrace{expected\ \#\ edges\ within\ group\ s }_{Need\ a\ null\ model}]$$

给定$n$个节点和$m$条边上的真实的$G$，构造重布线网络$G'$：

• 相同的度分布，但一致随机连接

• 把$G '$看作一个多图

• 节点$i$和节点$j$之间的$k_i$和$k_j$的期望边数为$k_i\cdot \frac{k_j}{2m}=\frac{k_ik_j}{2m}$，则$G'$的期望边数为：

$$G'_{edges} = \frac{1}{2}\sum\limits_{i\in N}\sum\limits_{j\in N}\frac{k_ik_j}{2m} =\frac{1}{2}\cdot \frac{1}{2m}\sum\limits_{i\in N}k_i(\sum\limits_{j\in N}k_j) = \frac{1}{4m}2m\cdot 2m = m$$

note：$\sum\limits_{u\in N}k_u = 2m$

由于图$G$的划分$S$的模块化为：

$$Q \varpropto \sum\limits_{s\in S}[(\#\ edges\ within\ group\ s) - \underbrace{expected\ \#\ edges\ within\ group\ s }_{Need\ a\ null\ model}]$$

则模块度可以定义为：

$$Q = \frac{1}{2m}\sum\limits_{s\in S}\sum\limits_{i\in s}\sum\limits_{j\in s}(A_{ij}-\frac{k_ik_j}{2m}) \\ =\frac{1}{2m}\sum\limits_{ij}(A_{ij}-\frac{k_ik_j}{2m})\delta(c_i,c_j)$$

其中，$A_{ij}$表示节点$i$和节点$j$的权重；和$k_j$分别为节点$i$和$j$所依附的边权值之和；$2m$为图中所有边权重之和； $c_i$是节点$i$所属社区，当节点$i，j$属于同一个社区时，$\delta(c_i,c_j)=1$ ，否则为$0$；$Q$模块化值取值范围为$[−1,1]$，如果组内的边数超过预期数，则为正，当$Q$大于$0.3-0.7$表示群落结构显著。

想法：可以通过最大化模块化来识别社区

Louvain Algorithm

Louvain是一种社区贪婪算法，用于社区发现，可以快速迭代，模型复杂度$O(n\log n)$，被广泛应用于研究大型网络 ，算法主要由两个部分组成：

• 首先，为每个节点选择最优的社区，使局部模块度达到最大

• 然后，对划分好社区的网络进行重构

• 上述两个步骤不断迭代，直至模块度不再发生变化

louvain与层次聚类的区别：Louvain的第一步是遍历每一个节点，尝试把它合并到一个社区中，等到遍历结束，进入第二步时，才把社区视为一个节点，而层次聚类算法中，每做一次合并，就把合并后的cluster视为一个新的cluster，计算cluster的中心。

image-20210305121908027

$\Delta Q$为多少的时候，可以将节点$i$移动到社区$C$？

$$\Delta Q(i\rightarrow C) = [\frac{\sum_{in}+k_{i,in}}{2m}-(\frac{\sum_{tot}+k_i}{2m})^2] - [\frac{\sum_{in}}{2m}-(\frac{\sum_{tot}}{2m})^2-(\frac{k_i}{2m})^2]$$

​

其中，$\sum_{in}$是$C$中链接权重或节点之间链接数的总和，$\sum_{tot}$是$C$中所有节点的所有链接值的总和，其中$k_{i,in}$是社区$C$内节点与节点$i$的边权重之和，注意对$k_{i,in}$是对应边权重加起来再乘以2，这点在实现时很容易犯错，$k_i$是节点$i$的度。

注意，还需要考虑推导出将节点$i$从社区$D$中取出的$a$，然后：

$$\Delta Q = \Delta Q(i\rightarrow C) + \Delta Q(D\rightarrow i)$$