【斯坦福cs224w-图机器学习】4. Community Structure in Networks

GNN

发布日期: 2020-11-20

Community Structure in Networks

讲解两个知识点：

community structure in networks（What）

how to detection of them（How）

回顾一下在lecture 3中学到的roles和communities的区别：

承上启下，上节课讲解Roles，从大家的社会常识来看，不同的角色汇聚一起构成了社区（社会）community，这节课顺水推舟讲解communities

上图是从community的角度来看待networks，感觉这样的方式才是我们最常用的吧，不然直接怼一张啥都没有的network给用户，用户会懵逼？所以，community之于network是非常重要的！

艺术来源于生活，科研也是~我们的community观点也来自生活，下面来看看社会学是怎么给我们motivations？😮

Motivations——From Society

网络其实是信息流（flow of information），那么对于网络中信息流有一个基本问题：信息是如何在网络中流通（传播）的？比如咱们流言蜚语是怎么在我们的社交网络上散播开来的？

由于图是由node和edge构成，所以分解出的两个子问题：

节点在信息流中到底扮演了哪些不同的角色？
不同的连接（比如长的或者短的）在信息流中扮演什么角色？

这里通过一个实践问题来研究——人们怎么找到新工作？（这是Mark Granovetter, part of his PhD in 1960s在他博士论文中的部分工作）

在大家的认知里，应该是通过亲近的朋友那里可以获得更多的信息。通过研究发现：新工作的信息来源自acquaintances(一般认识的人），而不是close friends。

上图中提出从两种角度来考虑friendship：

单纯从结构（也就是网络拓扑）上来说，将friendship看作一个边，能够跨越网络的不同部分；
- 如上所说，我们可以得知friendship的structural role是Triadic Closure。
考虑了人际关系的层面，我们知道人们之间的friendship有深厚和浅薄。

Granovetter在friendship的两个角度之间架起了联系的桥梁：

从信息角度上来看：
(1)长的edge可以将“较远”的人群和目前所在人群连接起来，从而获取更“不一样”的信息（找到新工作）；
(2)而结构性强的连接（edges）在信息层面上就显得比较冗余。（这也是人们找到新工作来自接触较少的人的信息的原因所在）

所谓的Triadic closure可以简单地理解为两个人拥有一个common friend；

结构上的三角闭合（Triadic closure) = 高聚合系数（high clustering coefficient）

从我们平时的认知是可以比较直观的理解triadic closure的：如果B和C有一个共同朋友A，那么：

（1）B很可能会接触到C（在与A 的接触时间中）

（2）因为B、C有共同的朋友，所以会相互信任

（3）A很可能会介绍B和C认识

【一个来自Bearman and Moody的研究】表明：青少年女孩如果社交网络的聚合系数很低，则容易有自杀的倾向

they want to define the structural strength of a friendship,which is called edge overlap：

从edge覆盖的定义：分子是i,j节点周围共同节点的集合（除去i,j两个node），分母是i,j周围所有node的集合（同样剔除i,j两个node）

所以从这个定义很显然，当i和j这两个node是两个小“block”的一个连接时候，覆盖=0（i和j的连接的这条edge看成是两个区域连接的一座桥），而Oij=1则意味相互的连接是很强的，同时这些连接可能也有点冗余。

先看蓝色的线，横坐标是打电话的次数（特别close的人，比如我和我妈妈，天天打电话，次数很多），电话次数越多，覆盖的值越大。那红色的线，是把网络中结构保持不变，而edge strength随机重分配后得到的线，是平的，也就是和打电话的次数无关。

这里不同颜色表示打电话的次数，红色表示打的次数较多，可以看到红色的部分集中在一些小区域中，而其他（例如绿色和蓝色）的edges就表示弱很多的联系。那如果我们保持网络结构不变，但是随机的干扰edge strengths（随机扰动），会出现怎样的结果？（如下图）

regardless of the network structure，随机赋值，这时候，红色的edges就不是像前面那个图只是集中在一些小区域了。

我们知道如果我们去掉两个cluster之间的那个连接，这两个部分就分开了，下面做这样的尝试：把edges从弱到强，和从强到弱连接的去除，去除后对这个网络的影响是怎样的（见下图）

当把那个弱连接的edge去掉后，网络中最大component的规模一下子就掉下去了，同样，去掉覆盖值小的edge，也得到类似的结果。：

无论是最初的社会学研究，还是之后的电话网络，无不证明了我们可以以下面这种角度来看待我们的网络：

Network Communities

在这一章节中，communities，clusters，groups以及modules都是一个概念，老师会都用到。

前面介绍了这么多，那么现在来研究网络community，什么是community？那就是前面所说的：网络中内部联系很多（很强）而外部（网络的其余部分）联系较少（较弱）的nodes集合

所以我们需要学习的是最后的输出是（如下图：除了个别节点判断错误，其余都是正确）:

下面进入正题：

什么是社区？

社区是紧密连接的节点集合

什么是划分partition？

一个整体划分成不同的不相交的子部分。（这和聚类的思想很接近）

什么是Modularity Q？

Q是用来衡量网络是否较好的被划分成多个社区的。

那这个Q如何衡量划分是否够好呢？

如上图的计算公式。组s内的edges数量和预期的edges数量之差，如果差别大，那么应该是分对组了。既然说到这个预期的edges数量，就需要定义一个空模型。

Modularity

我们要计算$Q$，所以我们需要一个Null Model，在这里它也是一个Configuration Model：

什么是空模型？

模型的定义其实就是为了“对比划分的结果和随机网络的差异”，给定一个m个连接，n个节点的网络G，构造一个重新分配的随机网络G’。

这里的G‘与lecture 3中的G’不相同，这里的G‘可以为multigraph；

老师解释了expected number of edges计算方法的正确性，是通过计算整体边的期望值证明的，具体可以参见iPad笔记。

我们之前是从cluster这样一个宏观的角度计算$Q$的，在上图中，我们细化到cluster里面的pair中，同时对$Q$进行正则化，保证它的范围在[-1,1]之间！！！（其中的数学看iPad笔记）

对于$A_{i,j}=1$这件事，我觉得并不太严谨。

这个计算公式太多求和符号，看上去不是很好处理，所以我们对其进行一个等价的变化：

这个modularity除了作为度量指标，其实还有一个非常大的用处，就是：对Q最大化——得到最好的社区划分。

Modularity Q 可以用来衡量网络划分为社区的好坏程度，那么最重要的还是原始问题，到底怎么发现社区？

Detecting Non-Overlapping Communities: Louvain Algorithm

Louvain Algorithm的核心思想：Maximize the modularity

一种贪心算法，时间复杂度为$O(nlogn)$，可能是因为树形结构的原因~

支持带权图

a heuristic algorithm：具有启发式，探索的算法；

dendrogram：树枝状图

这个有点像分层聚类（hierarchical clustering）的味道，老师也说Community Detection也算是一种聚类任务！

算法的概述如下：

关于Phase 1，老师的解释是：

if I move a node from it’s current community to another community，will the modularity increase？——keep moving every until I get stuck~

Partitioning and restructuring

老师说这个贪心算法最后一定会收敛的。。。

Phase 1: Partitioning

注意输出的结果跟操作时结点的顺序是相关的。

下面介绍一种全新的计算Modularity Gain的方法，它由两个部分构成，下面是第一部分：

我们以原来的Modularity of C来讲解一下式子是怎么得来的：
$$
\frac 1 {2m} \sum_{i \in C} \sum_{j \in C} (A_{i,j}-\frac {k_{i}k_{j}} {2m})\
= \frac 1 {2m} \sum_{i \in C}( (\sum_{j \in C} A_{i,j})-\frac {k_{i}} {2m}\sum_{j \in C} (k_{j}))\
=\frac 1 {2m} \sum_{i \in C}( (\sum_{j \in C} A_{i,j})-\frac {k_{i}} {2m}*\sum_{tot})\
=\frac 1 {2m} (\sum_{in} - (\frac {\sum_{tot}^2} {2m})) \
$$

Phase 2: Restructuring

上面的伪代码描述的非常详细，可以细细地品读~

Example

Summary

Detecting Overlapping Communities: BigCLAM

Non-Overlapping vs. overlapping communities

我们之前考虑的community都是要求每一个node只能从属于一个community，但是我们现实生活中的情景比这复杂多了，比如有的人拥有双国籍？🤔所以我们要考虑overlapping的情况！接下来就是讲解怎么得到具有overlapping性质的community~

Algorithm

Affiliation Graph Model(AGM)

another way to generate random graph

如上图所示，这个模型包含两个层次：Community Affiliation和Graph，是通过Community Affiliation得到Graph~

模型的参数包括：

Nodes $V$

Communities $C$

Memberships $M$

Each community $c$ has a single probability $p_c$：how likely nodes in this community to link to each other？