基于链接内容的社区发现算法（一）
Robust Detection of Link Communities in Large Social Network by Exploiting Link Semantics
Robust Detection of Link Communities in Large Social Network by Exploiting Link Semantics
这篇论文是我加入张老师实验室读的第一篇论文，寒假里草草读了一遍，感叹了自己垃圾的英文水平，上周除了上课和作业基本没做什么，一直在研读这篇论文。很幸运的是上周关于这篇论文的汇报我做的非常精彩，也不枉自己上周那么辛苦的肝了。
这篇博客用来记录自己研读时候的思考和整理。
整个论文的整体内容我将从四个方面介绍。分别是社区发现算法的背景和现存的方法、论文提出的模型和方法、试验和结论与讨论。
1. Background
1.1 社交网络的发展
- 社交对于世界各地各领域的人们来讲都越来越重要。随着社交网络的发展，越来越多的信息开始在互联网中聚集。
- 对于这些大数据的分析能够让我们更加熟悉网络的深层结构、了解用户行为和未来趋势。
- 社交网络中的一个重要的问题便是社区发现，通过社区发现我们能够为用户提供个性化推荐和异常行为的识别。
- 所谓的“社区发现”，就是将出现在社交网络中的用户节点划分成不同的组别。每个组的用户结点都有着某些相同的特征。
1.2 现存的方法
- 我们通常用一个图来表示社交网络。其中的点表示用户结点，其中的边表示用户之间的联系。
- 最初人们社区发现的算法是根据网络的拓扑结构，即让我们划分后的各个社区间的边的数量最少，社区内部点之间的边尽可能的多
- 之后，社区发现的算法得到改进，我们通过节点内容进行社区划分，即使得同一个社区内的结点内容尽可能多的相似。通过结点内容进行社区发现能够大大提升我们社区发现的效率。
- 同时我们发现，用户之间的链接，即图中的边也含有大量的信息。
这张图形象的表示了我们的方法和其他方法的区别。其中右边的图是基于结点内容进行社区发现的算法示意图，左边的图是我们基于链接内容进行社区发现的图。
我们可以看出现有的其他方法的问题：
- 1.只考虑了节点内容。考虑节点内容进行社区发现在有些时候有很高的效率。以微博用户的社区发现为例，当我们提供的内容是用户简介时，基于节点内容进行社区发现是很可以的。但是当我们提供的内容是用户之间发送的消息时，这其实是一种“链接内容”，我们需要将链接内容转换成节点内容，比如用户A发送的所有消息算成用户A的节点内容。这时候势必导致社区划分的不准确。
- 2.假设网络拓扑社区和结点内容社区的用户结点是一样的。两个用户间联系紧密，构成一个拓扑社区，但是他们聊天的内容可能是很五花八门的，两个人可能被分到不同的节点内容社区中去，这个时候现有的方法社区发现的效率就会下降。
- 3.每个社区仅仅有一个话题。比如右边的图把Music和Movies混在一起当作一个话题，而我们的方法（左边）含有两个话题。
- 4.仅仅用单个词汇进行社区标签。有时候我们可能会不知所云。而我们的方法用句子进行标签，便于理解。
2.The Model and Method
2.1综述
详见图片
2.2 详细分析
我们先来看看我们进行社区发现需要考虑哪一些因素：
- 拓扑角度：结点、链接
- 内容角度：单词、句子、话题
- 社区和话题群聚(topic cluster)
变量介绍
详见图片(难理解的内容都已经用中文进行注释)
所有变量的详细关系如下图所示
为了便于理解，我自己又画了一个图。
图左半部分就是根据拓扑结构进行社区发现，右半部分是根据节点内容进行社区发现。
现在，我们的模型已经建立起来了，我们的目标为以下三点：
具体算法
我们算法的整体思想是这样的：首先我们根据某标准把网络中的所有节点划分到不同的社区中（E-step），然后我们将提取每个社区中的关键词，来进行社区标注。（M-step）
我们再根据标注进行有监督的学习，对社区进行更精准的划分，以此来一遍遍迭代。
下面我们运用了极大似然的思想进行EM算法。
E-step：
我们进行期望化的变量是p，p代表着链接
现在p的取值是Jensen不等式的取等条件。
M-step：
下面我们要求式(3)的最大值，tau、 omega_ri、 y_rj都是可以通过直接求导求出来的。剩下的psai和fai的最大值我们再一次通过EM算法来求。引入变量p和h，运用JENSEN公式，p和h在取等条件时式子取到最大值。
下面我们给出整个算法的伪代码，看懂这个图整个算法的思路就差不多了。
