社区发现(一)：标签传播算法

1/什么是社区发现
    一个网络可能会被分割成多个社区，有点类似于我们常说的俗语“物以类聚，人以群分”
    在社交网络中，我们发现有些节点之间连接非常紧密，而有些节点之间连接比较稀疏，这些连接紧密的节点可以看做一个社区，而社区与社区之间“分水岭”较为明显。
    下图就展示了在一个网络中发现了3个社区：
复制代码

2/目前社区发现的分类
    分为两大类：非重叠社区发现和重叠社区发现。
    <1>非重叠社区发现：
        一个网络中，每个节点均只能属于一个社区，这意味这社区和社区之间是没有交集的。
    在非重叠社区发现算法中，有不同种类的算法：
        1)标签传播算法
           基本思想是：
              通过标记节点的标签的方式来更新未标记节点的标签，在整个网络中进行传播，直至收敛。
              其中最具代表性的标签传播算法是LPA：Label Propagation Algorithm
        2)模块度
           基本思想是：
              通过定义模块度来衡量一个社区的划分是不是相对比较好的结果，
              从而将社区发现问题转化为最大化模块度的问题进行求解。下一篇文章中会讲。
    <2> 重叠社区发现
        1)networkx k_clique 渗透算法
            k是节点的个数，如果k个节点之间两两相连，则这就是一个k个节点的社区，
            如果有另一个k个节点的社区与该社区有k-1个共同节点，则可以把2个社区连接在一起
       
3/标签传播算法
  简介：
     标签传播算法是一种基于标签传播的局部社区发现算法。
     基本思想:
        一个节点的标签依赖其邻居节点的标签，影响程度由节点相似度决定。
        这里的相似度是用权重来衡量的，并通过传播迭代更新达到稳定。
        
  算法过程
     <1>初始化阶段：每个节点都初始化自己的标签（可能只有一个标签，也可能同时有多个标签。）
     <2>传播阶段：遍历网络中的每一个节点，然后找到它的所有一度连接点。
                获取所有一度连接点的标签，
                找到权重最大的标签，或者出现次数最多的标签，投票思想
                如果同时有多个标签的出现次数一样多，则随机选择一个。
     <3>收敛判定阶段：
                遍历网络中所有的节点，找到当前节点的所有一度连接点.
                获取所有一度连接点的标签，并找到权重最大的标签，判定是否是自己的标签，
                如果判定都通过，则算法结束。
                为防止震荡情况出现，应设置一个最大迭代次数，达到最大迭代次数后也退出。
   
 标签更新的方式：
    标签传播方式分为两种：同步更新、异步更新。
    1、同步更新：在第t次迭代中，每个节点依赖的都是邻居节点上一次迭代t-1时的标签。
    2、异步更新：在第t次迭代中，每个节点依赖的是当前邻居节点的社区标签，
               若邻居节点已经进行了第t次的更新，则依赖的是t时的社区标签，
               若未进行第t次更新，则依赖的是t-1时的社区标签。
    
 优点
    <1>逻辑简单，时间复杂度低，接近线性复杂度，在超大规模网络下会有优异的性能，适合做baseline。
    <2>不需要定义优化函数，不需要事先指定社区个数算法会利用自身的网络结构来指导标签传播。
    <3>类似于聚类，无监督学习
    
 缺点
    <1>雪崩效应(一步错，步步错)：
       社区结果不稳定，随机性强。
       由于当邻居节点的社区标签权重相同时，会随机取一个。
       导致传播初期一个小的错误被不断放大，最终没有得到合适的结果。
       尤其是异步更新时，遍历节点的顺序不同也会导致最终社区划分结果不同。
复制代码

       举个例子，上图中展示了一次标签传播算法的流程
       初始化阶段，每个节点都以自己作为社区标签。比如a的社区就是a，b的社区就是b,c的社区就是c,d的社区就是d,e的社区就是e。当进入传播阶段，节点c的邻居节点共4个：a，b，d，e。而社区标签也是4个：a，b，d，e,假设随机取了一个a，则此时c就变成了a，如上图中的第二个图。如果是异步更新，此时b，d，e三个节点的邻居节点中社区标签均存在2个a，所以他们都会立马更新成a。如果c当时随机选择的是b，那么c就变成了b，那么a,d,e的邻居节点中均存在2个b,所以a,d,e就会更新成b，从而导致b社区标签占优，而最终的社区划分也就成b了。  
       
    <2>震荡效应：
       社区结果来回震荡，不收敛。
       当传播方式处于同步更新的时候，尤其对于二分图或子图存在二分图的结构而言，极易发生。
复制代码

      举个例子，上图中展示了一次二分图中标签传播算法的流程。
      在同步更新的时候，每个节点依赖的都是上一轮迭代的社区标签。当二分图左边都是a，右边都是b时，a社区的节点此时邻居节点都是b，b社区的节点此时邻居节点都是a，根据更新规则，此时a社区的节点将全部更新为b，b社区的节点将全部更新为a。此时算法无法收敛，使得整个网络处于震荡中。
      
4/算法实现
  输入数据格式：采用的是边表的数据格式，即数据共三列，分别是node_in、node_out、edge_weight

  优化方向
     初始化阶段改进
        人工标注或者采用算法提取一些紧密的子结构，确定好网络社区的雏形，再进行传播。
     传播阶段改进
        根据具体的业务场景，仔细定义边权重edge_weight，点权重node_weight，优化标签传播的传播优先度，一个良好的权重定义可以隐式的划分网络结构，更有利于社区发现。
复制代码