1. Community Detection in Networks
- 图中的社区识别任务就是对节点进行聚类
- networks & communities
网络会长成图中这样：由多个内部紧密相连、互相只有很少的边连接的community组成。
- 从社会学角度理解这一结构：
在社交网络中，用户是被嵌入的节点，信息通过链接（长链接或短链接流动）。
以工作信息为例，Mark Granovetter 在其60年代的博士论文3 中提出，人们通过人际交往来获知信息，但这些交际往往在熟人（长链接）而非密友（短链接）之间进行，也就是真找到工作的信息往往来自不太亲密的熟人。这与我们所知的常识相悖，因为我们可能以为好友之间会更容易互相帮助。
Granovetter认为友谊（链接）有两种角度：
一是structural视角，友谊横跨网络中的不同部分。
二是interpersonal视角，两人之间的友谊是强或弱的。
Granovetter在一条边的social和structural视角之间找到了联系：
- structure：structurally/well embeded / tightly-connected 的边也socially strong，长距离的、横跨社交网络不同部分的边则socially weak。
也就是community内部、紧凑的短边更strong，community之间、稀疏的长边更weak。
- information：长距离边可以使人获取网络中不同部分的信息，从而得到新工作。structurally embedded边在信息获取方面则是冗余的。
也就是说，你跟好友之间可能本来就有相近的信息源，而靠外面的熟人才可能获得更多新信息。
- triadic closure
triadic：三元; 三色系; 三色; 三重; 三合一;
community (tightly-connected cluster of nodes) 形成原因：如果两个节点拥有相同的邻居，那么它们之间也很可能有边。（如果网络中两个人拥有同一个朋友，那么它们也很可能成为朋友）
triadic closure = high clustering coefficient4
triadic closure产生原因：如果B和C拥有一个共同好友A，那么B更可能遇见C（因为他们都要和A见面），B和C会更信任彼此，A也有动机带B和C见面（因为要分别维持两段关系比较难），从而B和C也更容易成为好友。
Bearman和Moody的实证研究5 证明，clustering coefficient低的青少年女性更容易具有自杀倾向。
- 多年来Granovetter的理论一直没有得到验证，但是我们现在有了大规模的真实交流数据（如email，短信，电话，Facebook等），从而可以衡量真实数据中的edge strength。
举例：数据集Onnela et al. 20076
20%欧盟国家人口的电话网络，以打电话的数量作为edge weight
图中左上角overlap：0/6
图中右上角overlap：2/6
图中左下角overlap：4/6
图中右下角overlap：6/6
- 在电话网络6 中，edge strength（电话数）和edge overlap之间具有正相关性：图中蓝色是真实数据，红色是重新排列edge strength之后的数据（对照组）：
在真实图中，更embeded（密集）的部分edge strength也更高（红）：
相比之下，strength被随机shuffle之后的结果就没有这种特性：
从strength更低的边开始去除，能更快disconnect网络（相当于把community之间的边去掉）：
从overlap更低的边开始，disconnect更快：
- 从而，我们得到网络的概念图：由structurally embeded的很多部分组成，其内部链接更强，其之间链接更弱：
2. Network Communites
- network communites就是这些部分（也叫cluster，group，module）：一系列节点，其内部有很多链接，与网络其他部分的外部链接很少
- 我们的目标就是给定一个网络，由算法自动找到网络中的communities（densely connected groups of nodes）
- 以Zachary’s Karate club network来说，通过社交关系创造的图就可以正确预判出成员冲突后会选择哪一边：
- 在付费搜索领域中，也可以通过社区识别来发现微众市场：举例来说，节点是advertiser和query/keyword，边是advertiser在该关键词上做广告。在赌博关键词中我们可以专门找到sporting betting这一小社区（微众市场）：
- NCAA Football Network
节点是球队，边是一起打过比赛。通过社区识别算法也可以以较高的准确度将球队划分到不同的会议中：
- 我们可以通过最大化modularity来识别网络中的社区。
3. Louvain Algorithm
- Louvain Algorithm
是用于社区发现的贪心算法，O ( n log n ) 运行时间。
支持带权图和hierarchical社区（就可以形成如图所示的树状图dendrogram）。
广泛应用于研究大型网络，快，迅速收敛，输出的modularity高（也就意味着识别出的社区更好）。
- Louvain算法每一步分成两个阶段：
第一阶段：仅通过节点-社区隶属关系的局部改变来优化modularity。
第二阶段：将第一步识别出来的communities聚合为super-nodes，从而得到一个新网络。
返回第一阶段，重复直至modularity不可能提升。
如下图右下角所示：
- Louvain算法将图视作带权的。
原始图可以是无权的（例如边权全为1）。
随着社区被识别并聚合为super-nodes，算法就创造出了带权图（边权是原图中的边数）。
在计算过程中应用带权版本的modularity。
- phase2 (restructing)
将通过上一步得到的社区收缩到super-nodes，创建新网络，如果原社区之间就有节点相连，就在对应super-nodes之间建边，边权是原对应社区之间的所有边权加总。
然后在该super-node网络上重新运行phase1
图示如下：
- Louvain Algorithm整体图示：
- 在Belgian mobile phone network中，通过Louvain algorithm，可以有效划分出法语和德语社区：
- 本节总结
- modularity：对将图划分到社区的partitioning的质量的评估指标，用于决定社区数
- Louvain modularity maximization：贪心策略，表现好，能scale到大网络上
4. Detecting Overlapping Communities: BigCLAM
- overlapping communities
- Facebook Ego-network11
其节点是用户，边是友谊：
在该网络中社区之间有重叠。通过BigCLAM算法，我们可以直接通过没有任何背景知识的网络正确分类出很多节点（图中实心节点是分类正确的节点）：
- protein-protein interactions
在protein-protein interactions网络中，节点是蛋白质，边是interaction。其functional modules在网络中也是重叠的。
- 重叠与非重叠的社区在图中和在邻接矩阵中的图示：
- BigCLAM方法流程：
第一步：定义一个基于节点-社区隶属关系生成图的模型（community affiliation graph model (AGM12)）
第二步：给定图，假设其由AGM生成，找到最可能生成该图的AGM
通过这种方式，我们就能发现图中的社区。
- AGM可以生成稠密重叠的社区
- AGM有弹性，可以生成各种社区结构：non-overlapping, overlapping, nested
- 通过AGM发现社区：给定图，找到最可能产生出该图的AGM模型参数（最大似然估计）
- BigCLAM总结：
BigCLAM定义了一个模型，可生成重叠社区结构的网络。给定图，BigCLAM的参数（每个节点的membership strength）可以通过最大化对数似然估计得到。
