刚哥的公开课笔记：图机器学习（四）网路的社区结构

从角色到社区

社区和网络

我们通常认为网络看上去是这样的：

网络：信息流

  • 信息如何通过网络流动？
    • 节点在结构上扮演什么角色？
    • 不同的链接（“短线”与“长线”）起什么作用？
  • 人们如何找到新工作？
    • Mark Granovetter，1960年代博士学位论文的一部分
    • 人们通过个人联系找到信息
  • 但是：联系人经常是熟人，而不是亲密的朋友
    • 这令人惊讶：人们希望您的朋友能为您提供比熟人更多的帮助
  • 为什么熟人对我最有帮助？
  • 关于友谊的两种观点：
    • 结构性：友谊跨越了世界的不同网络部分
    • 人际关系：两个人之间的友谊的强弱
  • 结构性作用：三联闭锁
    • 如果两个人在网络中有一个共同的朋友，然后他们将成为朋友的可能性增加。
  • Granovetter在边缘的社会角色和结构角色之间建立了联系
  • 第一点：结构
    • 结构上嵌入的边缘在社会上也很强大
    • 跨越网络不同部分的远程边缘在社会上薄弱
  • 第二点：信息
    • 远程范围使您可以从网络的不同部分收集信息并获得工作
    • 结构上嵌入的边缘在信息访问方面是高度冗余的
  • 三重闭合=高聚集系数
    三重闭合的原因：
  • 如果B和A有一个共同的朋友C，则：
    • B与C相遇的可能性更大
      • 因为他们俩都和A在一起）
    • B和C互相信任
      • （因为他们有一个共同的朋友）
    • A有动机将B和C介绍到一起
      • （因为A很难维持两个不相交的关系）
  • Bearman和Moody的实证研究：
    • 聚集系数低的年轻女性更容易自杀

真实数据的边强度

  • 多年以来，格兰诺维特的理论没有得到检验
  • 但是，今天我们有了大型的“与谁对话”的图
    • 电子邮件，Messenger，手机，Facebook
  • Onnela et al。 2007年
    • 欧盟20％人口的手机网络
    • 边强度：＃电话呼叫数量

边重叠：

N（i）是节点i的邻居的集合

当边是本地桥的时候重叠是0

  • 手机网络
  • 观察：
    • 高度使用的链接具有高度重叠
  • 图例：
    • True：数据
    • Permuted strengths 置换强度：保持网络结构，但随机重新分配边强度

真实网络，真实边强度

移动通话图中的实际优势

  • 牢固的纽带更加嵌入（重叠度更高）

相同的网络，相同的边强度，但现在把强度随机改变

根据强度，移除边

根据重叠，移除边

Granovetter的理论导致了下面的网络概念图

网络社区

  • Granovetter的理论表明，网络由紧密连接的节点集组成
  • 网络社区：
    • 具有大量内部连接而很少有外部连接（到网络的其余部分）的节点集。

查找网络社区

  • 我们如何自动找到这种密集连接的节点组？
  • 理想情况下，这样的自动检测到的聚集将对应于真实组

例如：

社交网络数据：

  • 扎卡里（Zachary）的空手道俱乐部网络
    • 在大学空手道俱乐部中观察到社交联系和竞争
    • 在研究期间，冲突导致小组分裂
    • 分裂可以用网络中的最小限度来解释

通过在网络搜索中划分“查询广告商”图来查找微型市场：

NCAA橄榄球网络

节点：球队，边：球队间的比赛

  • 社区：紧密连接的节点集
  • 定义：模块 Q
    • 衡量网络划分为社区的程度的方法
    • 给定一个分区 网络分成不相交的s∈S：

空Null模型

  • 给定n个节点和m个边上的实数G，构建重新布线的网络G'
    • 相同度分布，但均匀随机连接
    • 将G’视为多图
    • 度为Ki和Kj的节点i和j之间的预期边数等于

（多重图形）G’中的预期边数：

模块化

图G的分区S的模块化

  • 模块化值的范围为[−1,1]
    • 组中边的数量超过预期的数量是正值
    • Q大于0.3-0.7意味着是重要的社区结构

等效的模块化可以写成

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

Louvain算法

  • 社区检测的贪婪算法
    • O（n log n）运行时间
  • 支持加权图
  • 提供分层社区
  • 被广泛用于研究大型网络，因为：
    • 快速
    • 快速收敛
    • 高模块化输出 （即“更好的社区”）
  • Louvain算法贪婪地最大化模块化
  • 每个迭代包括两个阶段
    • 阶段1：通过仅允许对节点社区成员资格进行本地更改来优化模块化
    • 阶段2：将识别出的社区聚合到超级节点中以建立新的网络
    • 返回第一阶段

第一阶段（分区）

  • 将图中的每个节点放入不同的社区（每个社区一个节点）
  • 对于每个节点i，该算法执行两次计算：
    • 将节点i放入某个邻居j的社区中时，计算模块化增量（∆Q）
    • 将i移到节点j的社区，该社区在∆Q中产生最大增益
  • 第1阶段一直进行到没有动作产生收益为止

当达到模块化的局部最大值时，即没有单个节点移动可以改善模块化时，该第一阶段停止。 注意，算法的输出取决于考虑节点的顺序。 研究表明，节点的排序对所获得的整体模块性没有重大影响。

模块化增益

如果将节点i移到社区C，∆Q是什么？

  • 这里：
    • Σin...中节点之间的链路权重之和
    • Σtot...中节点的所有链路权重之和
    • Ki，in…节点 和 之间的链路权重之和
    • Ki...节点的所有链路权重（即度）的总和。
  • 还需要推导ΔQ（D→i） 将节点i移出社区D。

第二阶段（重构）

  • 在第一阶段中获得的社区被压缩到超级节点中，并相应地创建了网络：
    • 如果相应社区的节点之间至少有一条边缘，则超级节点已连接
    • 两个超级节点之间的边缘权重是其相应社区之间所有边缘的权重之和
  • 然后，第1阶段在超级节点网络上运行

算法伪代码

比利时移动通信网络

两百万节点，红色是说法语的用户，绿色是说德语的用户。

总结：

  • 模块化
    • 将图划分为社区的总体质量
    • 用于确定社区数
  • Louvain模块化最大化算法：
    • 贪婪策略
    • 出色的性能，可扩展到大型网络

发现重叠社区：BigCLAM

不重叠社区和重叠社区：

Facebook：ego-network

蛋白质-蛋白质交互网络

社区

  • 第一步）
    • 为基于节点社区隶属关系的图定义生成模型
      • 社区隶属关系图模型（AGM）
  • 第二步）
    • 给定图G，假设G由AGM生成
    • 寻找可能产生G的最佳AGM
    • 这样，我们找到了社区

社区-关联图模型 AGM

  • 生成模型：社区关联如何生成网络？
  • 模型参数：
    • 节点V，社区C，成员M
    • 每个社区c都有一个概率pc

AGM的生成过程

  • 给定的参数（V，C，M，{pc}）
    • 社区c中的节点通过以概率pc掷硬币来相互连接
    • 属于多个社区的节点具有多次硬币翻转
      • 如果他们是第一次“错过”，他们将通过下一个社区获得另一个机会

AGM可以表达各种社区结构： 不重叠，重叠，嵌套、

不重叠

重叠

嵌套

利用AGM查找社区

给定一个图，找到模型F

  • 1）隶属图M
  • 2）社区数C
  • 3）参数Pc

图拟合

给定G时，如何估算模型参数F？

  • 最大似然估计
  • 给定真实图G
  • 查找模型/参数F

为了解决这个问题，我们需要：

  • 有效地计算P（G | F）
  • 然后在F上最大化（例如，使用梯度下降）

给定G和F，我们计算F生成G的可能性：P（G | F）

向P（u,v）释放AGM，会员有优势

BigCLAM 模型

  • 节点u，v链接的概率与共享成员的强度成正比：
  • 给定网络G（V，E），我们最大化L（F）

这是网络G的对数似然性-所有边缘发生和所有非边缘不发生的总概率

  • 优化：
    • 以随机F开头
    • 更新节点f的Fuc，同时固定所有其他节点的成员资格
    • 更新需要线性时间，单位为u
  • 梯度上升

进行梯度上升，在此我们对F进行细微变化，从而导致对数似然性增加

纯梯度上升速度很慢！然而：

通过缓存Fv，梯度步以u为单位花费线性时间

赞 (0)

相关推荐