英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
社区搜索问题和如何开一个成功的鸡尾酒派对
摘要
现在有很多研究都致力于社区发现。大多数的工作致力于发现社区结构仅仅依靠输入的图。然而，因为一些有趣的应用，人们对给定一些点的集合来寻找社区产生了兴趣。这篇论文我们研究一种基于查询节点的社区发现的变体即社区搜索问题，社区搜索就是给定一个图G和图中的一个查询顶点集合，我们想找到一个G的子图，子图包含查询节点并且是密度相连的。我们设计了一种方法基于最小度和距离限制，该方法利用一种最优化的贪婪算法来实现。我们首先描述了一系列单调性限制并且我们推广我们的算法，使得它可以计算出满足任何单调性限制条件的最优结果。最后，我们改进了这个贪婪算法并且提出了两种启发式算法，这种启发式算法可以找到规模不大于已给上限的社区。我们的实验基于真实的数据集，证明了我们的算法的有效性和结果的正确性。
关键字：图挖掘，社区发现，社会网络，图算法
1．前言
图是现实生活中最常见的一种数据结构，图数据在各个领域都有广泛的应用，包括生物、物理、社会科学和信息技术。随着大型网络实用性的提高，我们需要设计系统的数据分析工具，使得我们可以发明一种应用来探索数据中潜在的结构。最近几年，图和社会网络的社区发现吸引了一大批人的关注。它已经成为了图挖掘中最重要的最热门的研究问题。大多数的研究工作都致力于在一种先验条件下（仅参考输入图）来发现社区结构。然而，在很多应用场景中我们更有兴趣发现社区在给定一个结点集的情况下。例如，如果鲍勃和爱丽丝上同一门探戈舞课，凯乐是鲍勃的老板，那么鲍勃和爱丽丝构成的社区和鲍勃和凯乐构成的社区是有很大不同的。
论文中我们研究了一种社区发现问题的变体即社区搜索问题。社区搜索即输入一个图和一个查询结点集，任务是发现一个包含查询结点的且密度相连的子集。我们研究的这个问题有很多有趣的应用，比如社会网络分析、协同标注系统、查询日志分析等等，具体例子如下：
发现一个群体或组织一项活动：一些科学家获得了一些资金来组织一个研讨会。他们发现如果他们邀请一些同事或者和其他参会者曾经一起工作过的人，那么这场研讨会举办的成功率也就越高。
标签推荐：在社会媒体环境下，一个标签图联系着相似的标签。例如，一个照片分享门户中，如果他们经常同时出现在同一个相册集，那么这两个标签是相关的。一个照片有很多标签，系统可以推荐这个照片给那些具有相似标签的用户。这个推荐用户就是具有用户间具有相关联的标签。
生物：生物学家确定了一些蛋白质可以调节兴趣基因，他想要进一步研究参与这个调节过程的其他蛋白质。这个候选集可以通过找到蛋白质关系网络中包含原始蛋白质的密度子图。
其他的学者也在图数据挖掘领域研究了类似的问题，我们的论文也从这些研究中得到很多启发。例如，Faloutsos和Tong还有其他学者已经研究过这个问题并且发现了包含查询结点的子图。我们的方法主要的不同在于我们不仅可以发现包含查询节点的社区还可以发现有意义的社区。另外，我们采用一种图理论算法：我们首先基于子图的密度用公式表示出了目标函数，利用这个目标函数需要采用严格的方法来得到实用的技术和结果。
为了找到包含查询节点的密度相连的社区，首先需要给密度一个合理的定义，现在已知的一些方法有用子图的平度度或最小度来表示密度。下面我们讨论，平均度的缺点，平均度是敏感的即一个不相关的但是密度子图可能被连接到查询节点，因此会导致不想要的结果。因为这个原因，我们采用后一种算法即最小度。我们也给出了排除离查询节点较远的节点的概率，因为这些节点远离查询节点，因此这些节点与查询节点的关联性比距离近的节点和查询节点的关联性小。我们论文的目标是发现紧凑的包含查询节点的社区且满足最小度最大。
对于这个问题，我们设计了一种贪婪算法来计算最优结果。最小度方法和和距离限制有一个有趣的性质即他们是单调的，第四部分给出了单调性的具体定义。我们展现出这个贪婪算法可以给出最优结果（1）满足任意单调函数（2）满足任意数量的单调性限制条件。
遗憾的是，我们的贪婪算法不能处理有大小限制的社区发现算法。实际上，带有大小限制的社区发现问题是一个NP难问题。遗憾的是大小限制是一个很自然的约束，比如科学研讨会最多邀请100个参会者，生物学家最多研究50种蛋白质等等。
为了处理大小限制问题，我们修改了原来的贪婪算法，并提出了两种启发式算法可以发现满足给定上限的社区。这个启发式算法是得益于单调性限制的最优性，并试图满足大小限制通过设置可选择的单调限制来影响结果的大小。
论文的组织方式如下：下一部分是相关工作。第三部分我们定义了社区搜索问题，第四部分我们提出了贪婪算法和它的一般化加上单调限制和单调函数。第五部分，我们讨论了启发式算法，第六部分列出了实验结果，第七部分，总结全文和未来展望。
2.相关工作
我们的论文受到了很多社区发现和密度子图的研究的启发，包括密度子图的发现在理论计算机科学。我们简单的回顾了下面两种工作，由于篇幅限制给出了大量的参考文献。
连通子图：Faloutsos和Tong提出了寻找包含一系列查询节点的连通子图的问题。这些论文主要致力于在全局图结构上设计算法。这些算法基于electrical-current flows和自由行走等相关概念。主要任务是提取接近查询且相连的子图利用成熟的相似算法。后面的算法，Koren用CFEC精炼了相似性算法，提出了一种限制算法优化了CFEC算法。最近，Asur和 Parthasarathy提出了观点邻居的概念，为了在动态演化网络中确定邻居关系，表现出热点之间的连接关系，Cheng提出了上下文感知结构中连接查询节点的问题，这是第一次利用模块方法划分图，并且研究了社区水平的连通性。最后，Kasneci利用了一种基于自由行走的方法来提取信息量大的子图满足包含查询节点和密度相连。
我们的方法和以上的方法主要有两个不同。首先，我们希望提取包含查询节点的更有意义的社区而不是仅仅包含查询节点。第二，我们提出一种和理论方法相似的方法，把社区搜索问题变成一个图论问题。我们需要提出更严密的方法根据社区结构和理论计算科学。
社区发现：在大图比如社会网络或其他各种网络中发现社区是一个很大的研究方向。一种典型的社区发现算法是是模块算法。有很多论文研究过模块算法，并改进算法。例如，Brandes证明了优化模块是NP难的，Fortunato和 Barthelemy研究了结果限制问题，White 和 Smyth设计了一种光谱算法来优化模块。Agarwal 和Kempe提出了一种数学程序算法和更多算法其他社区发现算法包括最大流算法来发现密度子图，基于光谱算法的图分割算法，例如METIS算法和自由行走。以上的所有算法都是解决的静态社区发现问题，即没有参考查询节点。
密集子图问题：发现一个图的密度子图问题在理论科学研究中也得到了广泛关注。一个常见的优化目标是子图的密度，常常指节点的平均度。如果没有子图大小的限制，该问题可以在多项式时间内接解决。Charikar展示了本文中的算法可以得到近似结果。类似的贪婪算法Asahiro之前也研究过。如果加上了大小限制，发现子图大小刚好是k的子图是NP难的，解决这个问题的最好的算法的复杂度是n的a次方，a小于三分之一。最近，Andersen 和Chellapilla研究了具有上限和下限的社区发现问题。两种问题都是NP难的，在有向图或无向图中只能得到近似结果。
我们的工作和以上论文的不同在于，我们发现的密度子图是基于查询节点的另外，我们发现在有查询节点的情况下，平均度的方法将会得到不想要的结果，因此我们利用最小度和距离限制。
结构形成：最近Lappas研究了结构形成的问题，给定一个社会网络，每一个节点有一个标签我们需要发现一个子图交流花费最小我们可以看第四部分这些限制是单调的，因此可以容易的并入我们的框架。因此我们的问题是Lappas所研究问题的变体。团队需要根据最初的成员构成团队的优势在于可以计算加入单调性函数后的问题比如，最大距离和最小度。
3.问题定义
在本节中,我们介绍用我们的符号更正式的定义社区搜索的问题。我们给出一个无向图G =(V,E)边的集合E代表二进制之间的关系，顶点为V。例如在科学家合作网络,蛋白质关系网络、社交网络、电子邮件网络,查询图等。我们通过n表示节点的数目和m表示边的数量。当没有明确提及我们没有提出任何权重、标签和边在图中,然而,许多我们认为本文的概念适用于广义的情况下权重和标签。例如,可能会考虑节点上的标签说明是具有专业技能的人组成一个团队,完成项目,Lappas已经研究过了。节点的权重表示节点的重要性，就像网页排序算法中，边的权重表示节点间的关联程度。
除了图G =(V,E)我们也给出输入一组查询节点。这些节点形成了我们希望提取的社区。给定一个诱导子图H,考虑函数f测量提取的子图的好坏。我们希望f取大值如果H是紧密相连的。我们将讨论f的不同选择后，我们的问题的第一版:
问题一（一般的目标函数）给定一个无向图G=（V,E）一系列查询节点Q属于V，适应度函数f，我们的目标是找到一个子图H满足：
- H的节点包含Q
- H是连通的
- F(H)是最大的在所有可能的选择当中
注意这个假设输入图G是连通的，也可以推广到一般，查询节点不能属于不同的G的连通分量，因为这样就得不到结果，因此我们只考虑Q所在的连通分量。
对于适用度函数的选择，我们希望适应度函数可以捕获子图H的密度。一种方法是子图H中的边的数量，所有可能的边有条，即使最简单的定义这也是一个NP难问题，所以我们可以暂不考虑。还有两个其他的函数可以衡量子图的密度，（1）节点的平均度函数（2）节点的最小度函数，平均度函数还可以表示为，实际上密度函数在计算机科学领域已经得到了广泛研究。
然而，在所有的适应度函数的研究中都是基于没有给出查询节点的情况下。如果用在查找包含查询节点的子图的情况这些函数将不适用。例如图一，查询节点是xyz，直觉结果是社区xyzpq。然而，注意平均度会增加，如果我们把k6加入结果中，即结果为xyzpqrabcdef。实际上，k6中的节点和查询节点属于不同的社区。
这个例子就演示了上面的问题，为了提高平均度我们可能很容易的就加入了不相关的但是密度相连的社区到Q中。
因此，这篇论文的用所有节点的最小度来衡量密度。寻找最大最小度的方法有一个缺点就是对异常值很敏感。但是它对该问题没有影响，例如图一用最小度方法即可找到最优结果xyzpq。
Figure 密度的不同定义
另一种避免病态结果的方法是，设置一个距离限制。具体定义如下：用表示节点v和节点q之间最短路径的长度。如果v和q在不同的连通分量中，则为无穷大。对于图G中的一个节点v，我们定义节点v到查询节点的距离为
并定义
到查询节点的最远的距离。也可以用求和符号表示。
问题二：给定一个无向图G（V,E），和一系列查询节点Q，数值d表示距离限制，我们寻找一个子图满足：
- H的节点包含Q
- H是连通的
- H的最小度是所有可能结果中最大的
4.没有大小限制的社区
这一部分我们提出了一种社区发现算法。我们从特定的问题开始而不是最大化社区中节点的最小度。我们忽略距离限制。通过最小度目标函数的指导，我们提出了单调性的定义，我们初始化我们的算法以任意的单调性函数和单调性限制，包括距离限制。这部分我们假设没有大小限制。有大小限制的社区将在下一部分讨论。
4.1最大化最小度
我们首先提出了一种优化算法来解决问题二。我们的算法是一种贪婪算法，是一种Asahiro提出的贪婪算法的变体。Greedy算法的细节如下：
- 我们开始另G0=G，然后每一步进行删节点；
- 在第t步，我们考虑具有最小度的节点u在图Gt-1中；
- 结果，在第t步我们得到了图Gt通过删除节点u和节点u的边
- 这个算法终止在第t步如果满足：至少一个查询节点有最小度或查询节点不在连通
如果Gt是算法第t步的结果，我们用Gtrsquo;表示Gt的包含查询节点的连通分量。GREDDY返回一个G0表示每一步的执行结果中的具有最大的最小度的图。贪婪算法可以在线性时间内完成。建立一个列表来分别存放节点度为1hellip;n的节点，如果移除一个节点u，他的邻居的度将减少1，应该从d列表中移到d-1列表中。所以移动的次数是O（m）。另外，既然 每次最多减少1，给定一个节点具有最小度，我们在下一步可以确定最小度节点在O（1）时间。总时间为O（n m）。
明显的，贪婪算法给出一个最优结果。下面，我们假设d为节点数，有距离限制的社区发现将在下一部分讨论。
定理1：G为一个图，Q为一系列查询节点。贪婪算法可以返回一个最优结果，满足包含查询节点且最小度最大。
证明：另G0为一个该问题的优化结果，考虑贪婪算法的第t步，当G0的第一个节点被删除。Gt表示第t步的图。V是被优化的第一个点，所以G0是Gt的子图。暗示Gt一定有一个连通分量Gtrsquo;是G0的一个子图，否则，G0将是连通的。我们已知Gtrsquo;的最小度大于等于G0的最小度。既然v有最小度在Gt中，所以Gtrsquo;的每个节点u都满足：
表示Gtrsquo;有最优的最小度。
4.2单调性函数的概括
这一部分我们概括了前面各部分的结果。我们首先提出来单调性函数的概念，最小度函数也是其中一种。最后我们展示了贪婪算法可以用于发现各种单调性函数的最优结果。
定义1：单调函数。V是一个结点集，Gv表示V上定义的所有可能子图的集合。F是一个函数可以给每一个子图打出一个分数值，即。如果函数是单调非增函数需要满足G中的每一个节点和G的每一个子图H满足。我们
全文共7829字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[143016]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
