一、动机
从低秩嵌入的角度来看，现有的多种社团检测算法中有两类代表：随机模型（Stochastic Model）和模块度最大化模型（Modularity Optimization Model）。在这两种算法的设计中用到了非负矩阵分解和奇异值分解，这两种方法为线性映射。但是，真实的网络存在不同的非线性特征，使得这些方法不能很好地运用。目前，神经网络是一个非常好的非线性映射的方法，所以作者将深度学习应用于社团检测，提出了Nonlinear Reconstruction（DNR）算法。
二、贡献
1、 具作者所知，他们是第一次成功将深度学习用于社团检测的；
2、 提出了DNR模型；
3、 在DNR的基础上加入节点之间关系的约束，提出了semi-DNR模型
三、问题描述：
给定一个无向无权图 G(N,E) G ( N , E ) ， N N 为顶点数，EE为边数，寻找网络中的非重叠性社团。
四、算法
-
思路
作者结合了Newman提出的模块度（modularity）和自编码器，将模块度矩阵作为自编码器的输入，用欧氏距离和sigmoid交叉熵作为误差损失函数训练网络，最后用k-means对模型中的编码进行聚类得到社团。
-
算法过程
文中的深度学习是由堆叠的自编码器实现，单个自编码器的计算过程如下：
【IJCAI 2016】Modularity Based Community Detection with Deep Learning 阅读小记 -
算法 DNR
考虑到单独增加神经网络的层数会带来计算上的复杂，所以采用多个自编码器堆叠来实现深度学习，文中采用三个自编码来堆叠。堆叠的实现方式是：三个自编码器分别训练，如首先将 B 输入第一个，训练以得到最佳权值， 然后将第一个的编码输出 H1 H 1 作为第二个自编码器的输入，重复上述步骤，直到训练完第三个。所以在已知编码层输出的情况下，三个自编码器是互相独立的。如下图：
【IJCAI 2016】Modularity Based Community Detection with Deep Learning 阅读小记
最后在社团检测部分，对最后一个自编码器的编码层输出 H3 H 3 进行 k-means 聚 类。
-
算法 semi-DNR
该算法是半监督，在算法中引入了约束，该约束为：假设部分节点的归属社 团已知，并且如果两个顶点属于同一个社团时，他们的低维映射h应该相似， 然后再将该先验知识加入模型训练中。具体表现为，引入矩阵 ON×N=[oij] O N × N = [ o i j ] ， oij o i j =1 表示已知两个顶点 i i ，jj 属于同一个社团，构建损失函数
对于该做法我的理解为，直接计算两个顶点的h向量之间的距离，如果已知属于同一个社团，那么该距离就会产生作用，从而对权值调节起修正作用。然后将其和 Lθ(B,M) L θ ( B , M ) 线性结合起来，生成新的损失函数： 【IJCAI 2016】Modularity Based Community Detection with Deep Learning 阅读小记 【IJCAI 2016】Modularity Based Community Detection with Deep Learning 阅读小记
五、实验：
在两个人工合成网络（LFR和GN）以及6个真实的网络中进行实验，并且将DNR与6种算法对比，semi-DNR与2种类似的方法比较，评价指标为归一化互信息（NMI），最终表现良好。
参考文献：
[1]. Yang L, Cao X, He D, et al. Modularity based community detection with deep learning[C]// International Joint Conference on Artificial Intelligence. AAAI Press, 2016:2252-2258.
[2]. 自动编码器参考 https://www.cnblogs.com/taojake-ML/p/6475422.html