英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料
交互网络中的动态社区发现
Polina Rozenshtein, Nikolaj Tatti, and Aristides Gionis
赫尔辛基信息科技协会，阿尔托大学
摘要：通过大的事件间隔内的交互定义在线社交网络，例如，考虑那些在电话中至少有过一次联系的人或者在社交媒体网站中进行交流的用户。虽然这样的定义在许多图像挖掘任务中有很大的价值，但是它忽略了网络节点间发生互动的准确时间，致使它受到了很大的限制。
在本文中,我们研究的交互网络,它不仅考虑社交网络拓扑,而且还考虑到节点交互的准确时间。在一个交互网络中，一个边与一个时间戳联系，并且多边可能发生在相同的节点处。因此，交互网络可以提供更加细致的表示来揭露隐藏的网络动态现象。
考虑到在交互网络中发现社区这个问题，该社区比较密集并且会在短的时间间隔内出现新边。这样的社区代表着那些在特定时间情况下，相互作用的个人团体，比如在一个项目里的员工们，他们相互交流，加快了项目进程。我们证明了该问题是一个NP难解问题，并且通过调整用于发现频繁子图技术，提出了有效的算法。我们对合成和真实的数据集进行广泛的方法评估，表明了概念的有效性和算法的良好性能。
关键词：社区发现；图挖掘；社交网络分析；动态图；动态网络；交互网络
- 介绍
在社交网络中发现社区是社交网络分析最值得研究的问题之一。采用一组不同的算法工具：凝结方法，最小分割公式，步理论，波谱论等，已经提出来许多不同的方法。与这个工作线相比，发现那些大型网络缺乏清晰和明确的社区。【13,21】
缺乏明确定义的社区可能导致高度的互联互通和社区重叠。社区发现方法忽略网络节点间的交互时间加剧了社区重叠现象，例如，相同类型的链接表示在爱好俱乐部或者工作同事里的朋友。随着可用数据量的增加，我们不仅可以分析底层拓扑结构而且可以分析交互的准确时间。分析这样的交互事件可以显示更多关于网络社区的结构和动力学信息。想要更加具体，参考以下示例。
例1：来自不同欧洲机构的一群研究人员，他们正在研究一个大项目。这些成员每天一起生活，并且分别参与该项目无关的其他任务。每隔几周或者几个月，即在交付成果或者项目会议之前，他们会进行一次大讨论。
例2：一群Twitter用户，对技术产品和特定的智能手机感兴趣，他们评论相关博客，对彼此帖子间的讨论非常活跃。尽管他们的互动是稀疏的，但却能维持很长的时间，在新产品发布后，这种情况会明显加剧。
这两个例子的观点表明社区不是孤立的。社区成员不仅会和内部人员发生交互也会和外部人员发生交互。如果忽略了交互的相互作用，只考虑到静态社交网络拓扑，那么这些社区将会被隐藏且不被发现。只有考虑到时间的交互实例，社区成员才有可能识别它们。在上述例子中，许多交互发生在社区成员之间，并且每次交互的时间间隔相对较短。
在本文中，我们将上述例子形式化。假设网络节点间的交互事件都是已知的，在此前提下，我们考虑网络交互。这样的交互网络有电子通信、电子邮件通信网络、提及和评论的网络社交媒体和协作网络等。因此，在许多应用领域，交互网络数据集已经非常丰富。
在交互网络环境下，我们研究社区发现问题，这些社区非常密集并且它们的边在很短的时间间隔内出现。尽管在静态图中的相关问题是多项式时间可解，但我们证明这个问题是一个NP难解问题。对于我们定义的这个问题，我们在发现频繁子图相关文献的启发下，提出了相应的解决算法。我们通过实验验证了该算法的有效性以及假设的正确性。也就是说，发现能够满足我们需求的社区是可能的，即在大量短的时间间隔内发生频繁的交互。
- 假设与符号说明
一个交互网络由有个节点组成的集合和节点间个时间戳的集合构成。
其中
假设交互是无向的，一对节点在不同的时间戳可能发生多次交互。相反的，不同节点在同一时间可能发生多个交互。
对于一个交互网络，将边的集合和成对的节点相联系，因为它们至少有一次交互（认为作为交互网络沿着时间轴的边的“投射”）。
考虑到交互网络，网络是一个在它的边没有时间戳的标准图。我们将定义为拓扑网络或者是潜在网络。
考虑到交互网络以及节点的子集，我们定义感应互动网络，其中由交互组成，这些交互的终端节点都在集合中。
同样考虑时间间隔，其中作为起始节点，作为间隔的终点。我们定义一个间隔跨度使得时间连续即。
定义一个时间间隔集合作为一个非重叠时间间隔集合，。的跨度就是所有跨度的总和。
考虑到一个交互网络和时间间隔，定义拼接交互网络，其中是在中提及的交互。
为了定于关于一组时间间隔的拼接交互网络，上述公式可以以简单明了的方式进行扩展。通过收集来自个人时间间隔边获得，即，其中。
感应互动网络和拼接交互网络的概念提供了挑选交互网络子集的两种不同的方法；一个是基于节点子集而另一个是基于时间间隔。这篇文章的核心概念即动态社区的定义取决于两个子集挑选策略。尤其，对于一个动态网络，节点的子集和时间间隔的子集，定义一个动态社区，作为由集合里的节点与在出现在中与集合里的节点的交互集组成。用更正式的术语来说，即定义为拼接交互网络，其中是感应交互网络。
为了衡量动态社区的质量，我们依赖于密度的概念。我们撤消了对密度是静态图的定义，比如，一个交互网络的拓扑网络。我们也检查了静态图的子图密度问题。
考虑到静态图，其中边没有时间戳，图的密度是边和顶点比的两倍。
问题1（子图密度）：在考虑静态图的情况下，查找顶点密度最大的一个子集。
不同于查找最大范围问题这样的NP难解问题，发现密集子图是一个多项式时间可解问题。此外，有一个线性时间两因素近似算法【2,8】。该算法删除了最低度的重复节点，来获得连续子图。该算法返回这些子图中最密集的一个。
- 交互网络中的密集社区
考虑一个交互网络，我们目标在于发现节点集合和时间间隔集合，因此子图在内相对密集。为了确保子图的时间跨度较短，我们对时间间隔集合强加了两种类型约束：1）对的间隔约束；2）对总长的约束。我们简单的说明一下折两种约束。对于我们下面所提出的发现密集动态社区这个问题，假设一个质量分数来衡量交互网络中社区的密度。
问题2：假设一个给定的质量分数能够衡量交互网络中由节点和时间间隔跨度定义的社区的质量。假设给定时间间隔数量一个预算和总的时间跨度的预算。我们的目标是发现一组节点集合和时间间隔集合能够最大化，其中。
第一个约束条件表明最多有的间隔而第二个约束条件要求总的时间不能超过。这两个约束条件是必要的：假设质量分数随着时间跨度增长，如果放弃第二个约束条件，那么我们将总是选择总的时间跨度。然而，这样的方法不能捕获我们想要发现的动态社区的直观知识。另一方面，如果我们丢弃第一个约束条件，那么我们将通过在每个个体边建立一个时间间隔为0的方式挑选个体边。换句话说，对间隔数量的限制强加于解决方法发现的时间持续性是非常必要的。
关于衡量社区质量的分数函数，我们提出的方法是：在限制节点集和时间间隔集后，拓扑网络的密度。
即我们计算在时间间隔中的节点间发生的交互数量的两倍，然后用除以这个数。
3.1 复杂性
我们开始对在交互网络中发现动态社区问题的复杂性进行分析（问题2）。
命题1：问题2 的最终结果定义为完全NP问题。
证明：给定一个交互网络，预算和一个临界值，我们需要回答当时，是否存在一个节点集和一个时间间隔集能够满足两个预算约束条件。
这个问题很显然是一个NP问题。为了证明该问题的难度，我们从Vertex Cover中引用了下降。在这个例子中，指定一个图和预算，探寻是否存在一个集合并且这个图的每条边至少与中的一个节点邻近。
已知图由个节点，条边和预算组成。定义一个交互网络。节点集由和个额外辅助节点组成，而且边集定义如下：首先，我们考虑个显著时间点。我们考虑在时刻所有附加节点间的交互并且这些附加节点的每个节点。任意安排中的节点并且让表示第个节点。在时刻，将与中它的所有邻接节点相连接。
针对问题2，假设存在解决方案和，其中预算。我们要求包含所有的节点而包含和与顶点覆盖相关的时间点。
首先证明，否则进行上述假设。因为剩余的时间间隔仅有的边，所以个生产密度最多有条边。用替换挑选的时间间隔，重置为附加节点。这个方案证明有密度，与现实相矛盾。
现在，假定。。一种直截了当的计算表明如果附加节点不在该方案考虑范围内，那么将这些附加节点添加到中总是有利的。一旦该设想被证明，就可以更深入的表明从中添加任意缺少的节点也能改进密度。因此，。
假定。计算器的前两条术语都与时刻的边有关。剩余的条边都来自于剩余的时间间隔。当且仅当时间间隔包含来自的边的时候，相关节点才可能覆盖每一条边，完成节点数的降低。
- 社区发现算法
在这部分，针对问题二，我们提出了算法。因为该问题是NP难解问题，我们提出一个迭代算法，通过优化节点集或时间间隔集并保持另一个不变来改进算法。
交互的优化算法的两个目标是提高计算问题。一个问题是降低发现频繁子图的困难度，另一个则与覆盖范围有关，它甚至是一个NP难解问题。其次，正规化交互优化算法的两个问题。
问题3：已知一个交互网络，发现一个具有预算，质量分数的密集动态社区问题。假设已知节点集作为输入，查找一个时间间隔集，使得最大化，其中。
问题4：在一个质量分数为的交互网络中发现密集动态社区的问题。假设给定一个时间间隔集作为输入，查找一个节点集，使得取最大值。
提出的算法开始于一个原始的时间间隔集，而且，在收敛前通过迭代方式解决上述两个问题来获得解决方案。该方法的伪代码在算法1中给出。但是，这个迭代算法不能为返回的结果提供保证。然而，它在接下来的命题中被证明，并且证明非常直截了当。如果它们能保证正确输入另一个成分，那么交互优化问题返回正确结果是非常令人满意的。
命题2：给定一个交互网络，作为其对于问题2的一个解决方案。那么（1）就是给定的问题3的一个解决方案；（2）就是给定的问题4的一个解决方案。
在接下来的两部分4.1和4.2中，我们更加细致的介绍了迭代算法中两个子问题的解决方案。在4.3部分，我们讨论算法的初始化。
4.1 查找最佳节点集
问题4的目标是在已知时间间隔集的条件下，查找一组最佳的节点集。假设给定一组时间间隔，作为在内发生交互的拓扑网络（即交互网络中通过拼接的拓扑网络）。节点满足：
因此，在（静态）图中查找最佳节点集和查找密集子图问题（问题1）是同意义的。其次，已知时间间隔集，可以在多项式时间内查找到最佳节点集。在实现过程中，我们使用了在第二部分概述的Charikar线性时间算法，提供了两因素近似保证。
4.2 查找最佳时间间隔集
给定节点集，查找一组最佳时间间隔集，我们给出了针对迭代算法第二个子问题的解决方案。不幸的是，尽管这是普通社区发现的一个子问题，但仍然是NP难解问题。这个声明的验证就是命题1验证的一个简化版本。
我们将查找最贱时间间隔问题看成多预算（MCMB）最大限度覆盖问题的一个例子。
问题5（MCMB）：已知一组集合，它们的权重为，一组子集的集合，的费用函数映射的每一个子集到一个正数和的预算参数，查找一个子集，使得取最大值，其中。
当时，该问题就是一个标准的预算最大限度覆盖问题。尽管这个问题仍然是一个NP难解问题，但是参考Khuller et al.存在一种近似算法，能够获得的近似比率【17】。但是，这个算法需要列举三个子集的所有集合，实际操作是不可行的。
该优化问题也可以看成在多线性约束下使子模块函数最大化的一个例子。Khuller et al.中提出了能获得近似比率的多项式算法【18】。不幸地，该算法对于任何都不具有实用性。
为了研究发现一组时间间隔集是如何与最大覆盖相关的，首先设定一个边集（在没有时间戳的中出现的交互）和对于每一个时间间隔，创建一个子集，其相关交互发生在中，并包含所有的边。有两个费用函数。第一个预算约束要求允许的时间间隔必须小于，而第二个则是时间跨度约束。
因此，我们需要解决上述定义的有两个预算约束的MCMB问题。我们提出了两个解决防范，它们都属于对于最大覆盖标准的贪婪算法。这两个方法的不同之处在于如何满足预算约束。第一种方法通过贪婪算法合并两个预算约束，而第二种方法设置一个参数来控制违反该约束的数量，并且通过二进制搜索优化该参数。
最大覆盖的标准贪婪算法即筛选一个集合，对于它的费用，该集合有最近覆盖成分的最好比率。根据这个想法，提出了下面的贪婪算法。给定当前的一个时间间隔集，我们发现间隔有最好比率，其中。在比率中的分子就是被间隔覆盖
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[28937]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
