DEMON框架简述

《以局部优先的方法发现分层和重叠的社区》，这篇论文是导师给我，让我看一下，实现一下里面的算法，但是发现在作者的个人网站上已经有实现的版本了(传送)，所以就整理一下论文思路就好了。首先还是翻译一下Abstract和Instruction两部分。

论文标题：Uncovering Hierarchical and Overlapping Communities with a Local-First Approach

作者：Michele Coscia 哈佛大学肯尼迪学院

论文于2014年10月发表于ACM Transactions on Knowledge Discovery from Data

摘要：复杂网络中的社区发现是许多实际应用中的非常有趣的问题，特别是在社交和信息网络中的知识提取任务中。然而，许多大型网络常常在整体范围内缺乏特定的社区组织。在这种情况下，传统的图划分算法无法让嵌入在模块结构中的潜在知识显现出来，因为他们强加（impose）了一个自上而下的网络全局视图。我们提出了一种简单的本地优先的社区发现算法，能够揭示真实复杂网络中的模块化组织。这是通过民主（democratically）方式实现的，通过使用标签传播算法，让每个节点在其对全局系统观察有限的情况下（即其自我邻居）为其周围的社区投票。然后，这些本地社区分层合并，在全局级别上公开网络的模块化组织，并识别重叠的组或者组的组。我们用最先进的重叠和非重叠社区发现算法测试了这种直觉，发现我们的新方法在获得社区的质量上明显由于其他方法。我们在基准网络和真实网络上都进行了测试，通过使用提取的社区来预测关于多个真实网络节点的元数据来评估划分质量。我们还提供了一个可能的解释，来解释为什么真实世界的网络包含重叠社区，以及DEMON捕获它们的背后的逻辑。最后，我们展示了我们的方法是确定性的，完全增量的，并且的时间复杂度有限，因此它可以用在Web规模的真实网络上。

简介：在过去的十年中，复杂网络分析已经成为数据分析和挖掘中最令人兴奋的领域之一。其中最多产的子领域之一是复杂网络中的社区发现，简称CD。在（网络、社交或信息）网络中，“社区”的概念被直观的理解为一组彼此非常相似或相近的个体，而社区外的人没有那么相似。在网络术语中，这常常被转换为寻找彼此紧密连接且与网络其他部分稀疏连接的节点集。社区发现可以看作是传统数据聚类的一种网络变体。能够有效检测这些结构的算法是非常有用的，其应用范围从有针对性的疫苗接种和疫情预防到病毒式营销，再到许多Web数据分析任务上，比如发现一群人在网络上的信息交流，数据压缩、聚类和取样。

社区发现的经典问题定义在小型网络中找到一种非常直观的对应关系，在小型网络中，较密集的区域很容易通过肉眼观察来识别，而在中型和大型网络中，问题则变得困难的多。在全球范围内，网络的模块化结构非常少，因为在更大的范围内，系统的组织变得极其复杂。截止2013年3月，Facebook的关系网图包括了超过11.1亿个节点，如图1所示，即使考虑其中一小部分，CD任务的难度也是非常大的。我们描述了15,000个节点之间的连接，即少于总网络的0.00002%。即使是在这么小的子集中，也不容易识别出明显的组织，大的网络是无法明显用肉眼去分析的。通常，上万个节点的可视化会是一个没有结构的黑团。在这种情况下，通用的社区发现算法往往得到的是没有意义的社区结构，因为它们通常试图在整个结构中检测，返回一些大型社团和很多小的分支。通常，按照自顶向下顺序叠加会导致失败（superimposing an order with a top-down approach leads to failure）。

相反，人类的眼睛善于在简单的网络中发现更密集的区域。即考虑到一个大网络的局部片段中出现的具有内聚性的节点组的结构。但是局部意味着什么呢？常识告诉我们，人们善于找出认识自己认识的人的原因；因此，每个节点大概都有一个不完整的，但清晰的，关于他所处的社交团体以及围绕他的社交团体的愿景（vision）。图2有效的说明了对CD问题利用这种思想的结果。在这里，我们选取了之前提到的15K个节点中的一个，提取处我们称之为“自我-自我”网络（ego minus ego）。即去掉了自我节点和依附于它的边的自我网络。突然之间，自我周围的一切都有了意义，一些群体很容易被发现。这些群体对应于高中和大学的朋友、不同工作场所的同事和在线社区的成员（我们之所以知道所有的细节，是因为被选中的节点是这篇论文的作者之一）。自我（ego）是所有这些群体的一部分，并且知道它周围的特定子集也是这些群体的一部分。也许，不同的自我对同一个邻居有着不同的看法。

所有这些透视图（perspectives）的联合，或者类似的社区可以在不同聚合级别上合并在一起的分层视图，创建了网络的最佳划分。换句话说，如果连接到A和B的所有节点都认为节点A和节点B在同一个社区中，那么它们应该被分组到同一个社区中。如果他们被连接到同一社区的大多数或多个节点考虑，那么他们可能是更高级别社区的一部分。这是通过一种民主的自下而上的挖掘方法实现的：每个节点依次给出其周围社区的透视图，然后将所有不同的透视图合并到一个重叠的结构中。这种重叠的结构可以被看作是一个扁平的社区覆盖，也可以以分层的方式合并到一起。

在大量的关于CD的论文中，检测网络模块化结构的一般方法是开发一个特定的（贪心）算法，启发式测试一个质量函数，然后返回从全局结构中提取出的一组社区。由于全局和局部组织结构的差异，这种方法通常不适用于大型网络。为了解决这个难题，我们建议改变思路。 既然我们的社区定义（community definition）在小网络中可以很好的工作，那么我们就应该只在小范围网络应用它。我们提出了一种简单的本地优先的方法用来发现复杂网络中的社区，方法是让隐藏的网络模块化组织从本地模式中出现。

本质上，我们采用民主的方法来发现复杂网络中的社区。我们要求每个节点为其本地视图中出现的社区投票。因此，我们将算法命名为网络模块化组织的民主估计（Democratic Estimate of the Modular Organization of a Network），或简称DEMON。在实际应用中，我们提取了每个节点的自我网络，并在这个结构上应用了标签传播CD算法[Raghavan et al.2007]，忽略自我存在，自我将由它的邻居判断。然后，我们将网络中每个人的投票公平地结合起来。这种组合结果是一组（重叠）的模块，这是对全局系统中真实社区的猜测，不是由网络外部观察者做出的，而是由网络本身的参与者做出的。然后，我们要么在这里停止这个过程，要么将重叠的社区重叠的部分折叠为单个节点，用与他们共享的节点数量的比例作为加权链接将他们连接起来。我们重新用相同的流程来处理，并为我们的社区层次结构获得一个额外的级别。我们对每个层级重复这个过程，直到将整个网络折叠到一个社区为止。

我们的民主算法是增量式的，它只允许对进化网络中新加入的节点和边重新计算。尽管如此，DEMON理论上具有较低的时间复杂度。我们方法的核心还有一个有趣的特性，即很容易并行化（parallelizable），因为执行独立计算只需要ego网络信息，而且很容易在MapReduce（Dean and Ghemawat 2004）框架中组合。但是在MapReduce框架中的后处理FlatOverlap过程是不可解的。DEMON的特性支持它在大量的真实世界场景中使用。

我们提供了对DEMON一个广泛的经验验证。在我们的实验环境中，我们特别感兴趣的研究是我们能发现哪些有用的知识。我们将用我们的方法得到的结果与选定的4种既有重叠又有不重叠的最先进的算法进行了对比测试，因为我们认为，在不同的社区中有相同的节点是社区发现算法应该允许的关键属性之一：在线社交网络已经证明，个人是许多不同社区和兴趣群体的一部分。

首先，在已建立的基准设置中测试了算法的性能,能够生成具有重叠社区的有向加权网络。其次，我们对比了在真实网络上的性能。在这个环境（setting）中，我们使用了一个多标签预测器并将提取的社区作为输入，目的是能正确的分类在现实中附加到节点上的元数据。我们的数据集包括亚马逊、IMDB以及GovTrack.us。最后，我们尝试提供一个关于为什么社交网络包含重叠社区和为什么DEMON能很好的发现它们的解释。

这篇论文是我们之前工作[Coscia et al.2012]的一个延伸。这个扩展提供了以下几个贡献：

-通过引入返回层次社区结构的概率，扩展了DEMON算法

-介绍了基于基准网络的实验评价

-我们对实验部分进行了扩展，引入了一个新的数据集，包括多维网络，并对社交网络重叠问题作出了解释

-我们介绍了DEMON假设的生成方法（introduce the formulation of the DEMON assumption of the community generation），为开发更好的网络基准铺路

-通过将DEMON放在社区发现算法分类中，我们扩展了相关工作部分