文摘

装备传感器移动设备允许用户参与各种社交网络服务。我们专注于附近移动社交网络环境中用户可以通过移动设备共享信息来自不同的地方,当他们接近。因为人们更容易分享信息,如果他们可以受益于共享或如果他们认为感兴趣的信息,可能存在社区结构,多用户共享信息组合在一起。社区附近移动网络代表社会群体在连接当人们接近。我们认为(即信息的影响。,specify who shares information with whom) as the connection and the space and time related to the shared information as the contexts. To model the potential information influences, we construct an influence graph by integrating the space and time contexts into the proximity-based contacts of mobile users. Further, we propose a two-phase strategy to detect and track context-aware communities based on the influence graph and show how the context-aware community structure improves the performance of two types of mobile social applications.

1。介绍

确定社区是一个重要的研究课题在传统以及在线社交网络(1,2]。一个社区紧密连接的节点/用户组是一个这样的社区之间的联系是稀疏的。与智能手机等移动设备的日益普及,社区结构的研究变得更加重要。例如,人们可能会从他们所参观的地方收集信息并与他人分享这些信息他们相遇接近当他们移动。距离这里暗示他们的移动设备在彼此的WiFi和蓝牙的传播范围。确定社区等附近的移动网络经常会导致更多的成本效益信息传播通过共享信息只与那些可能感兴趣的和更有针对性的查询只问那些可能的信息。减少通信开销使用移动设备的社区最终将减少能源消耗。在本文中,我们研究如何为社区建设提供更多的相关信息,更有效地支持在附近移动网络应用程序。

现有的工作,详细的部分2向社区、集群移动用户仅仅基于接触发生当用户接近。这些纯contact-based社区只显示在同一社区的人们联系更频繁或长时间接触。他们不认识的地方,当联系人发生时,或是否有信息共享通过接触与否,因此失去重要的信息在附近移动网络:这些联系人相关的上下文,也就是空间和时间相关的信息共享。换句话说,两个用户经常接触或更长时间只意味着他们彼此的通信范围内,但这并不一定意味着他们可以分享更多的信息。因此,采取一步更好支持附近社会信息共享的应用程序,一个更好的群落结构应当整合联系人与时间和空间的上下文。

在本文中,我们解决现有工作的不足通过构建基于潜在信息的连接影响当人们接近构造环境敏感群落结构。这些信息影响与时间和空间上下文的信息来源。让我们看看校园的场景。爱丽丝去学生中心,她学会了免费的电影票被放弃,而鲍勃访问他学到了游戏的娱乐中心。学生可以分享的信息后一定时间内他/她得到了信息,说5个小时。假设在5小时内访问学生中心,爱丽丝遇到克里斯然后鲍勃。而在5小时内访问娱乐中心,鲍勃遇到大卫和爱丽丝。所以,爱丽丝可以告诉克里斯和鲍勃的学生中心事件,而鲍勃能告诉大卫和爱丽丝的娱乐中心事件。上下文感知社区为学生中心由爱丽丝,鲍勃,和克里斯;上下文感知社区的娱乐中心由爱丽丝,鲍勃和大卫。 However, assume that outside of the 5 hours window, Emma frequently encounters Alice, Bob, Chris, and Dave. If only considering contacts, then a pure contact-based community consists of all these five students.

类似于contact-only社区,社区环境敏感也建造使用长期移动用户移动模式的接触时间和接触频率被认为是随着用户访问过的地方。因此,环境敏感的社区比纯contact-based更明智的和有意义的社区和可以用来更好地支持数据服务在附近移动网络消耗更少的能量。考虑前面的校园场景中,当艾玛想知道关于学生中心的信息,与上下文感知社区,她查询可以只发送到学生中心相关的三个成员组成的社区;但与纯contact-based社区,她查询必须被发送到社区由五名成员组成。的沟通成本和能源成本获取信息是减少使用上下文感知社区。

在这项工作中,我们综合时间和空间上下文与接触构造一个新的图,“影响图”,开发了一种两阶段策略探测基本上下文感知社区和跟踪上下文感知社区的发展。我们的评估结果表明,该环境敏感群落结构具有良好的社区属性使用一些标准的社会指标。在进化过程中,它在这些社区属性是一致的,有效地反映信息的影响,在更新和有效的社区。进一步,它是有效的和有效的在支持两种类型的移动社交applications-event共享和查询事件。

剩下的纸是组织如下:在部分2,我们提出相关的工作。节3,我们提出假设和问题陈述。节4,我们的方法构建的影响图。节5我们的方法检测和跟踪环境敏感的社区。节6,我们现在的环境敏感群落结构与实证数据集的结果。节7,我们现在的结果应用上下文感知社区移动社交应用程序。

2。相关工作

检测和社区结构的进化是一个研究的主题在传统的社交网络(3]。一个方法跟踪社会进化是基于历史的特点。例如,Facetnet [4]研究社区在一个统一的检测和演化过程,在群落结构在给定的时间步是由观察到的网络数据和先验分布由历史社区结构;Evo-NetClus [5]研究异构网络的进化multityped社区的问题,提出了一个模型来生成net-clusters在每次的窗口,这是通过决定自然集群数量和考虑历史影响net-clusters同时之前的时间窗口。另一种方法来跟踪社会进化是基于大量离散事件。进化的行为交互图(6]从不重叠的快照捕获有趣的事件交互图和使用这些事件来描述复杂的个人和社区的行为模式;进化基于事件的社区追踪7)描述了一个社区进化模型的生命周期特征是一系列的重大事件,提出了一个简单的方法涉及匹配社区发现在连续时间步骤单独快照图来识别和跟踪社区;同样,GED (8]进化提出了社区发现算法基于七个类型的事件,包括持续萎缩,增长,分裂,合并,溶解,形成,考虑社区成员的数量和质量之间通过提供一个平衡的社区包含很多但是不重要成员和社区包含只有少数但关键成员。

尽管社区结构起着重要的作用在社会网络分析(9),研究社区在移动社交网络在很大程度上仍然是不完整的。最近的作品之一(10)提出了一种两阶段检测和重叠社区的进化框架动态移动网络,但它假定一个无向未加权的图和生成网络使用基准(LFR重叠11)进行评估。它并没有解决如何构建图构建社区在移动社交网络。其他最近的研究表明,在移动社交网络社区已经形成基于全球联系图(12,13],分布式的地方遇到[14,15),或者只是用户接近[16,17]。没有一个现有的工作包括任何时空背景下的社区建设。

简而言之,将时间和空间上下文与联系人建立社区附近移动社交网络是我们的工作区别于现有的工作。

3所示。问题描述

为了表示时间和空间上下文,我们采用的概念点利益(PoIs) (18]。与频繁的用户保持PoIs的地方很受欢迎,他们可以使用各种定位技术确定。我们假设用户在一个山芋可以获得PoI的事件和存储在他们的移动设备上的事件。每个用户都有一个惟一的用户id,一个流动剖面与一系列的接触和PoI访问,一组PoI事件的时间当用户获得他们,和一个用户影响一生指定时间用户愿意分享。例如,在校园的场景中,鲍勃在娱乐中心听到游戏事件,他愿意使用移动设备来存储事件5小时为了分享未来遇到的学生。在这种情况下,Bob的用户影响一生个小时。

在图1,有四个PoIs 20(使用小矩形来表示)和移动用户(使用小圆圈来表示),一些用户在哪里走出PoIs(移动方向是使用箭头来表示)。移动用户访问PoIs的在不同的时间,可以影响在他们停留在PoIs PoI事件。之后,他们可以进一步影响其他手机用户通过他们的移动设备与PoI事件如果他们遇到以外的其他用户相应的PoI随时期满前他们的影响力。一旦事件信息到达用户以外的山芋,这可能进一步转发给其他用户(即。,影响其他用户)。因此,信息影响脉动进位的方式继续。

我们正在研究的问题在这工作是如何考虑时间和空间上下文时形成的社区,构建社区可以更有效地支持信息的影响。换句话说,我们的重点不是在社区建设的新算法,它是关于时间和空间上下文融入社区建设。这个问题分解为三个问题:(i)构建社交图基于用户移动配置文件;(2)构建基本上下文感知社区和动态更新环境敏感社区反映进化网络;和(3)使用动态社区支持移动社交应用程序。

4所示。影响图

在本节中,我们介绍了影响图,直接加权图嵌入所有联系人以及空间和时间相关的上下文。影响图在下一节将用于社区建设。

影响图是基于潜在的信息影响移动用户之间的PoI事件。的潜在信息的影响发生接触时确定如下:PoI的潜在信息的影响从用户用户只有当存在PoI外的接触位置,计算用户的次数的总和访问PoI(即。,user可以直接获得PoI事件)和用户的次数一直在接触其他用户潜在的影响对PoI信息吗(即。,user可以被其他用户的影响),在用户这种接触发生之前影响一生。换句话说,是由两个直接和间接影响接触PoI的事件。

在形式上,图是由产生影响,在那里是一组用户,是一组两个用户之间的直接加权边缘,然后呢是一组PoIs。那里是一个有向边的顶点到顶点如果用户的影响图可能会影响用户。换句话说,如果用户参观过一些PoIs或已被其他用户的原发性卵巢功能不全影响事件,然后遇到用户期满前用户一生的影响。更正式,当用户和用户相会的时间,用户的潜在信息的影响用户被表示为一个元组吗,在那里在网络PoIs的总数,是芋泥,是关于PoI潜在信息的数量的影响当发生联系。的重量积累是一个元组的所有用户之间的联系和用户:。这个优势的定义不同于纯粹使用联系人,在两个用户之间存在一条边之间是否有联系。影响图,两个用户之间的联系发生并不一定意味着他们之间的优势如果没有用户信息的潜在影响。例如,如果用户没有访问任何PoI或和PoI事件不会受到其他用户或用户一生的影响已经过期之前遇到用户从用户,那么就没有优势用户。

4.1。一代的用户移动配置文件

为了构造图的影响,我们首先需要生成用户移动配置文件。典型的流动配置文件的用户包括时间当用户进入或退出PoI的时候用户与其他用户联系。更正式,一个用户的流动配置文件可以使用一个时间标记序列事件来表示。有三种类型的事件:(i)用户输入一个山芋(2)用户退出PoI,(iii)两个用户联系。

图2样品是直接翻译为Alice和Bob移动配置文件,在坚实的箱子贴上PoI(学生中心,娱乐中心,或库)显示时间,鲍勃和爱丽丝在PoI和连接与其他用户显示与用户联系。

4.2。施工的影响图

使用移动配置文件生成,我们可以使用以下步骤构造影响图。(1)做一个移动配置文件基于时间归并排序。(2)扫描集成用户流动剖面发现所有潜在的双向信息中任何两个用户之间的影响为每个PoI接触。注意潜在信息的数量的影响包括两个部分:(i)的数量PoI访问当用户可以直接获得来自PoI的事件,和(2)的数量与其他用户联系潜在影响对PoI的信息,因此用户也可以通过接触的影响。(i)和(ii)都应该发生在用户的影响。PoI的次数,我们用户的次数计数出口PoI(即。,the number of events在影响一生)集成移动概要文件。然而,如果接触PoI内发生(即。,the users have not yet exited PoI),然后用户被认为是self-influenced关于PoI的事件因为这些用户可以直接从PoI获得信息,而不是从另一个用户。在这种情况下,关于PoI的影响不计入重量。(3)把所有用户的顶点,把计数为每个PoI的潜在信息的影响从一个用户到另一个的重量直接影响图像边缘。

考虑图2作为一个例子。集成移动概要文件可以如图所示3,“”、“”、“”、“”和“”爱丽丝代表,鲍勃,克里斯,戴夫,艾玛,分别和“”、“”和““代表图书馆,娱乐中心,学生中心,分别。在每一次瞬间,事件是由““意义的用户进入PoI”,“意义的用户出口PoI,或称““意义的用户和用户在接触。

图4影响图是基于图吗3假设Alice和Bob都影响一生个小时。体重元组中的值代表图书馆潜在信息的数量的影响,娱乐中心,分别和学生中心。例如,爱丽丝和鲍勃在上午11点联系。在11点前5小时,爱丽丝曾经参观了学生中心而Bob参观了娱乐中心。因此,爱丽丝有一个潜在的信息影响鲍勃再分类学生中心,而鲍勃有爱丽丝对于娱乐中心的潜在信息的影响。因此,体重从爱丽丝鲍勃是元组,重量从爱丽丝鲍勃是元组。

5。环境敏感群落结构

5.1。检测基本上下文感知社区

在第一阶段我们的方法,我们形成了基本的社区使用的影响图。有多种方法来发现社区,其中大多数是基于模块化的集中优化方法(19)或当地的小团体渗流方法(20.]。我们选择应用CPMd算法(21],有向图版本的知名集团渗滤法(CPM) [20.]。使用基于小团体渗流方法的优点如下:(i)它是本地没有分辨率限制(即。,它可以检测到小社区)集中式模块化优化方法,(ii)的定义模块的基础上派系实际上是基于链接密度,所以连接更集中在社区,和(3)它允许社区之间的重叠。

CPMd使用指导派系(完全子图的大小)发现模块直接链接。它还使用一个链接权重阈值显示的强度直接链接。我们使用紧密联系/边来表示这些链接的重量不小于和薄弱环节代表其他链接。分数的联系的比例是紧密联系的数量超过总数的链接图的影响。对于每个选定的价值,CPMd链接权重调整阈值,最大的社区变成了第二大两倍。此外,至少有一半的链接应紧密联系的最佳阈值(即。,the link fraction应不低于0.5)。

社区环境敏感,我们发现社区关于每个PoI通过运行CPMd PoI-specific子图的算法的影响图。子图只包含强相关PoI的链接。这样,环境敏感群落结构构造的原发性卵巢功能不全相关的社区,表示为。环境敏感群落结构的意义是,用户有更多的潜在的信息互相影响与PoI-specific信息组合在一起,因此用户可以根据上下文确定他们的社区的信息。此外,社区可以重叠,一个用户可以属于多个社区PoIs不同或相同的芋泥。

自从链接权重取决于影响寿命和移动配置文件,一生中最重要的因素影响形成的社区结构。例如,使用图在图的影响4,通过设置和,我们可以构建环境敏感的社区结构。有两个社区,一个用于娱乐中心与爱丽丝,鲍勃,和戴夫和另一个学生中心与爱丽丝,鲍勃,和克里斯。然而,如果Bob改变他一生影响到8小时,那么社区关于学生中心将由四个成员(即。艾玛是补充说,除了爱丽丝,鲍勃,和克里斯)。

5.2。跟踪不断变化的环境敏感的社区

良好的社区应该灵活的进化模型和自动学习社区在每个时间步,而相邻时间戳的社区应该是一致的(5]。在第二阶段的方法中,我们提出一个简单但有效的方法有效地维护我们的社会结构,而自适应更新社区作为用户交互随时间变化的。最常用的符号符号部分中列出了本文。

根据讨论部分2,我们的方法是分类的社会进化方法基于重要的离散事件,但我们也考虑社区所反映的历史继承的特点保持相同的最优标准和值在构建社区。作为讨论的部分5.1,我们构造的基本使用CPMd社区。我们选择最优和分数值的方式联系影响图不少于0.5,和最大的社区不大于两倍的第二大一个在所有关于所有PoIs社区。然后,更新发展的影响图与实际用户之间的信息的影响。跟踪基于进化发展的社区影响图,我们使用相同的中使用值作为初始社区的形成。然而,我们更新这只有偏离初始值在一定的误差范围内。所有这些都是为了确保有足够的紧密联系在整个影响图和构建社区是重要的而历史特征。

自CPMd构造社区紧密联系的基础上,添加或删除一个节点本身不会导致不稳定现有的社区,除非导致链接权重(我将发生重大变革。e,导致一个新的强有力的链接将链接的添加,或一个强大的链接变得脆弱,因为增加的)。更具体地说,处理一个新的强有力的链接可能涉及处理一个或两个新的节点,和新节点可能会成为一些社区的一部分。同样,删除一个强大的链接可能会导致删除相关的节点从他们的社区。因此,我们不需要显式地处理任何节点添加或删除但只需要覆盖处理添加或删除时紧密联系。我们也注意,添加和删除的紧密联系是由不仅链接权重的变化,而且变化的。整个过程的社区更新(关于PoI参与每个链接更新)链接更新算法所示1。在以下部分中,我们将解决三个案例参与更新的社区。

5.2.1。添加一个强烈的联系

假设从节点没有直接联系来,或从来是一个薄弱环节。当体重增长的联系或以上,成为一个新的强有力的链接。有四种可能的一个新的强有力的链接:(i)在一个社区(即。,两个和是在同一个现有社区)(图5(一个));(2)在重叠社区(即。,两个和在一些现有社区的重叠部分)(图5 (b));(3)连接不同社区(即和都在不同的社区(和可以在重叠社区))(数据吗5 (c)- - - - - -5 (d));(iv)(即连接一些noncommunity结构。,至少有一个和与其他节点的联系,没有任何社区内)(数据吗5 (e)- - - - - -5 (g))。

定理1。社区构建的基于链接密度,一个新的强有力的链接在一个社区或连接与其他社区或社区noncommunity结构不应该分裂或摧毁的社区。

证明。这是因为社区分裂或破坏只发生在社区内的紧密联系为链接density-based社区建设越来越稀疏。自添加新的强有力的链接不会降低链接密度,它不会导致社会分裂或破坏。

根据定理1,我们可以处理每个新联系紧密的可能性如下。(我)保持当前的群落结构完整(图5(一个))。(2)社区合并可能发生的任何子集重叠社区(图5 (b))。为每一对社区包含,找当地的派系包含直到一个集团包含两个社区的另一个重叠节点(不包括和),标志着“合并”如果发现两个社区。(3)社区的社区合并可能发生的任何子集包含和(图5 (c)),或者之一和可能包含其他的社区(图5 (d))。每一对的社区包括和分别找到所有地方派系包括,标志着两个社区如果存在一个“合并”连锁集团由这包括任何其他节点在两个社区;否则,“合并”的其他节点如果存在一个社区集团在包括任何其他节点只有两个社区之一。(iv)如果连接社区noncommunity结构,noncommunity结构或可能包括的社区或(图5 (e)(图)或可能形成新的社区5 (f))。要做到这一点,包括为每个社区或,“合并”相邻如果派系到社区在相邻的社区的派系,否则,找到所有地方派系包括和“创造”一个新的社区连锁集团由。如果连接两个noncommunity结构的noncommunity结构和可能形成新的社区(图5 (g))。要做到这一点,找到所有地方派系包括和“创造”一个新的社区连锁集团由。社区的标记为“合并”,“合并”成更大的群体中,每一个社区标识“合并”与至少一个其他的社区。

5.2.2。删除联系紧密

一个直接链接从节点来,当其链接的重量低于增加,它就会变得软弱。有四种可能:删除联系紧密(我)是在一个社区或重叠社区(即。,两个和在同一个社区或重叠社区)(数据吗6(一)- - - - - -6 (d));(2)是连接不同社区或noncommunity结构(例如,和不共享任何社区)(数据吗6 (e)- - - - - -6 (f))。

定理2。社区构建的基于链接密度,移除一个强大的连接与其他社区或社区noncommunity结构不应该分裂或摧毁的社区。

证明。这也是因为社区分裂或破坏只发生在社区内的紧密联系越来越稀疏。以来的一个强大的社区外链接不降低社区内的链接密度,它不会导致社会分裂或毁灭。

根据定理2,我们可以处理每个摧毁强大的链接如下:(i)社区破坏数据6(一)- - - - - -6 (b))或拆分(数字6 (c)- - - - - -6 (d)为每个社区参与)可能发生;(2)保持当前的社会结构(数据6 (e)- - - - - -6 (f))。算法2显示了如何识别应该分裂或摧毁的社区由于删除一个强大的链接。

5.2.3。更新链接权重阈值

我们设置一个错误阈值链接的一部分。当有足够的链接更新导致情况链接分数差异大于阈值的错误或低于0.5,我们更新的链接权重阈值(见算法3)所以有足够强大的链接形式的社区。记得在算法1的增加,(只有当)可能导致的紧密联系,和减少(只有当)可能会导致增加紧密联系。

6。绩效评估

性能研究,我们需要使用经验数据集都位置/ PoI和联系信息。特别是室内PoIs的提取位置信息,利用无线AP访问比使用手机发射塔访问或GPS位置;为了获取联系信息,使用蓝牙接触比使用其他近距离评估技术,因为它最合适的通信范围。我们所知,有两个可用的数据集包含无线AP访问和蓝牙联系人:UIM [22,23]和宽谷Nodobo [24]。UIM收集通过专用的联合WiFi /蓝牙框架(25)在2010年3月27日用户来自伊利诺校园,大部分的WiFi和蓝牙定期跟踪记录;Nodobo收集通过一个通用手机遥感软件对手机使用的痕迹从2010年9月到2011年2月27日高中的学生,和更少的WiFi访问记录和蓝牙为每个用户接触比UIM由于高中学生活动和关注收集WiFi /蓝牙痕迹。我们使用UIM所有评估这项工作因为它包含足够的记录。

UIM WiFi痕迹。无线跟踪收集每30分钟。有5614无线AP mac电脑的无线所有27个用户我们考虑的痕迹,和有效的无线AP mac 985(即不偶尔发生。,至少27次发生在整个数据集在我们的评估)。然后,我们应用星聚类算法(26在WiFi APs);我们得到约200集群,每个集群代表了PoI。注意,可以小芋泥作为建筑内部的办公套件。

UIM蓝牙痕迹。蓝牙痕迹收集每一分钟。除了27的蓝牙mac用户我们以前认为,还有其他7671蓝牙mac电脑蓝牙这些27用户的痕迹,和蓝牙mac电脑的数量经常接触是123(即。在整个数据集,至少100名接触者在我们的评估)。因此,我们也考虑这123蓝牙mac电脑,然后我们总共有150用户。

通过结合WiFi和蓝牙的痕迹,我们可以获取用户的机动性和PoI访问(为每个用户每30分钟更新一次)和用户联系人(为每个用户每分钟更新一次)。我们构建一个集成的用户移动配置文件和训练集分成两个部位(从2010年3月1日至3月10日,2010年)建造的基本社会结构和测试集(从3月11日,2010年,3月19日,2010)研究进化的群落结构及其对应用程序的影响。注意,这些用户没有移动配置文件只有接触其他用户可以获得可用的蓝牙痕迹。他们仍然可以通过接触的影响也进一步影响他人。因此,所有用户被添加到图的影响。

在文献中,没有标准的标准评估社区结构。最常采用的是模块化的评价指标(19和归一化互信息27]。然而,模块化有不同的变化在不同的社区支持重叠社区发现算法。归一化互信息来自信息理论和使用地面真理(实际社区)作为基线;因此,并不适用于我们的工作在地面真理是未知的。为了利用基于CPMd当地社区结构的特性,我们采用内部成对相似性(IPS)指标用于基于贪婪局部优化社区检测方法(28]。IPS措施之间的平均相似度对节点在社区内。它可以用来评估社区检测算法支持重叠社区和不需要地面真理作为基线。除了平均IPS,我们使用平均社区的规模和平均数量社区PoI的社区结构。

研究进化的实际信息影响,我们让每个用户self-influenced PoI事件时参观PoI。根据我们之前的研究(29日,30.),严重影响群落结构,所以我们保持评估不同的群落结构。此外,我们不同同时在构建基本的社会结构自构造影响图只有很少有较高的派系。的选择范围随着选择满足标准中讨论部分5。此外,我们也有所不同研究其对群落结构的影响。此外,我们考虑两个社区更新频率——“每天更新”(即。,the community structure is updated daily after processing all link updates occurring on that day) and “update per link” (i.e., the community structure is updated for each link update).

我们第一次评估最终的社区结构,9天的测试期间已经演变UIM数据集的不同的值。因为大导致少新的强有力的联系,进一步导致合并,创建社区,它最终导致更多、更小的社区里面有更高的IPS社区。

图7显示的影响最后的社区结构,适度的值和(建议在图的讨论8)。我们观察(a)如图7(一),当增加,平均IPS增加;“每个链接更新”会导致更高的平均每天“诱导多能性”比“更新。”(b)如图7 (b)时,社区的平均尺寸减少每天增加,和“更新”会导致更大的平均社区规模比“更新链接。”(c)如图7 (c),平均每PoI社区增加时增加和“每个链接更新”会导致平均社区PoI比“每天更新。“注意,当,原链接部分后构建基本的社区结构是1,导致没有更新或在社会进化,也会导致相同的社区结构每个链接“更新”和“每天更新。“因此,社区结构有许多社区平均IPS和更大的平均尺寸低于高。当,将更新自保持更新。我们观察到当平均IPS不会增加太多,而社区的平均尺寸显著减少可能导致用户参与不足。因此,我们选择最优值下列评估。

图8显示的影响在最后一个社区结构和。我们观察(a)如图8(一个),当增加,平均IPS减少;“每个链接更新”会导致更高的平均“诱导多能性”比“每天更新,特别是对于规模较小的值。(b),如图8 (b)时,社区的平均尺寸增加每天增加,和“更新”会导致更大的平均社区规模比“更新链接。”(c)如图8 (c),平均每PoI社区减少时增加和“每个链接更新”会导致平均社区PoI比“每天更新。“所有这些都是因为大导致较慢的和更少的拆分和破坏的社区即使这些社区已经变得松散。一般来说,所带来的影响在上述指标并不重要。因此,我们选择的中值下列评估。

图9显示的影响在最后一个社区结构和。我们观察到,“每个链接更新”会导致平均IPS略高,平均社区规模较小,平均每PoI社区比“每天更新。“这些观察与结论的影响是一致的和。一般来说,两个社区的更新频率之间的差异很小。因此,我们可以使用“每天更新以下评价社区进化。此外,当增加,平均IPS增加因为PoI在更高的用户之间的影响;涉及社区的平均尺寸增加,因为更多的用户在更高,平均每PoI社区增加,因为有更多的PoI的影响也在更高更多的用户。由于重叠允许在上下文感知社区结构,产品的平均社区规模和平均社区/ PoI也增长增加。

图10显示了社会性质演变每天使用“每天更新。“天0代表了基本社会结构由UIM数据集的训练集。每天不断变化的群落结构波动的性质和两个相邻之间不要改变太多天相对于总体波动。这意味着随着时间的推移不断发展的社会结构是一致的,满足社区发展的目标中讨论(5]。在图10,我们也比较的社区属性上下文感知群落结构(“环境敏感”)与纯contact-based群落结构(“contact-only”)使用相同的数据集。纯contact-based社区结构是基于一个无向图中每条边联系连同它的重量代表了两个用户之间的联系。其第一阶段使用CPM构造基本相同的社区和CPMd在构建基本环境敏感的社区结构,和它的第二阶段使用部分中给出的算法5但无向链接和派系。的结果图10表明,纯contact-based群落结构有更低的平均IPS。请注意,纯contact-based社区结构是相同的所有PoIs;因此,它有一个更大的平均社区大小以及更多的社区,它变化更频繁地在进化过程中由于更多的更新,从而导致更多的社会分裂和合并(即。,越来越大的波动。总之,上下文感知社会结构具有较高的相似性在社区和更一致的进化比纯contact-based社区结构。此外,我们也评估社区属性在使用“每个链接更新”(没有显示在图10因为结果是接近使用“每天更新”)。值得注意的是平均IPS当使用“每个链接更新”在演化过程中不断增加。这意味着不断发展的社会结构变得越来越频繁地更新社区凝聚力。

最后,表1显示链接的数量每天添加和更新的时间每天群落结构与英特尔(R)的核心服务器(TM) 3.40 GHz CPU使用“每天更新”(乌利希期刊指南)和“每个链接更新”(推)。结果表明,(i)的更新时间发展的社区结构是远远低于施工时间的基本社会结构和(2)“每个链接更新”消耗时间略高于“每天更新”将更多的更新和更频繁的处理摧毁强大的链接。这些结果表明,我们的社区更新技术确实有助于减少社区跟踪时间。进一步,我们比较每天添加到链接的数量影响图的链接添加到联系图。结果表明,影响图的链接的数量总是低于20%的链接的数量联系图。中的链接联系图和最受欢迎的PoI的影响图(即。,the most visited PoI by the mobile users) using the entire dataset are shown in Figures(11日)和11 (b),分别。这个验证我们的直觉的影响图的链接的数量远低于联系图。这是因为许多联系人不存在信息的影响。这也意味着社区建造使用纯接触图形在大多数现有的工作是不准确的表示地面实况图链接联系以来并不总是意味着潜在信息的影响。总之,我们发展的社区结构是有效地反映信息更新社区的影响和有效。注意,减少相关的链接图的影响导致较小的和更少的社区比使用联系图,从而减少通信开销的信息共享是附近移动社交应用程序。我们将验证这个直觉在下一节中使用两个移动社交应用程序。

7所示。以社区为基础的移动社交应用

上下文感知社会结构构建和更新一个集中的服务器上基于用户移动配置文件收集,然后分发给所有用户对未来在支持应用程序使用。我们提出两个应用程序在附近移动网络。这些应用程序使用社区的优点是双重的:(i)用户分为各种子集更本地化的信息共享和(2)信息共享可以以不同的方式处理根据用户社区会员。

应用程序可以确定社区更新的频率。例如,它可以使用一个网络服务器实时收集用户信息的更新,然后立即触发更新的群落结构,也可以使用离线服务器定期收集用户配置文件更新,然后定期更新群落结构。在以下应用程序中,我们假设一个离线服务器正在使用和采用“每天更新”。对于每个应用程序,我们评估其性能与更新社区每天使用UIM数据集的测试集。PoIs的事件发生,我们不指定任何事件生命周期或更新。我们假设当用户每次访问芋泥,只有一个新事件生成用户的期间。然后,我们比较了应用程序的性能时使用环境敏感群落结构与contact-only群落结构(即。使用纯contact-based)。

7.1。不要错过:以社区为基础的事件分享

在这个应用程序中,用户访问一个地方与遇到用户访问共享事件发生之前,但现在外面那个地方。每个用户拥有一个活跃的事件(即。,the event is still within the user’s influence lifetime) forwards it to those encountered users who are within the same community regrading the PoI of the event. If the receiver has visited the PoI of the event before, he will view the event; otherwise, the event is discarded. In addition to implementing this application using “context-aware” communities and “contact-only” communities, for comparison, we also implement a baseline approach—“epidemic” where a user forwards the events to all encountered users.

图12(一个)展示了共享成功率,它是成功的事件分享的数量(即。,those events which have been delivered to at least one user who has visited the PoI of the event before) over the number of total events being shared (i.e., the number of PoI visits of all users since one event per PoI visit is assumed). “Contact-only” has higher sharing success ratios in the first two days, but it falls below “context-aware” in the following days. This is because the update of context-aware community structure is PoI related; it gathers more relevant users for each PoI than contact-only community structure. Figure12 (b)每成功显示感兴趣的用户的平均数量达到共享。“环境敏感”股票事件比“contact-only”在进化过程中感兴趣的用户。图12 (c)显示应用程序的成本通过事件的平均数量每成功转发分享。“环境敏感”比“contact-only介绍低得多的成本。“平均减少事件的转发成本约为24.7%。这是因为“contact-only”收集用户不管PoI的相关性,从而导致更多的不相关的用户参与活动共享。

进化的每一天不同的性能基于PoI每天发生的高层互访和接触,所以性能不能从日常相比。此外,这项工作的重点不是在设计一个有效的转发协议对于移动社交应用程序,所以我们只采用一个基本传播协议在这工作。如果使用了更好的转发策略,应用程序的性能可能会有所改善。总之,上下文感知社区事件在事件交付共享是有效和高效的事件代理成本。

7.2。是什么:以社区为基础的事件查询

在这个应用程序中,用户将特定的地方查询关于这些地方的事件。更具体地说,一个查询用户活跃的用户到达PoI之前,并创建一个新的查询后用户离开了PoI。

每个用户将PoI发起一个查询有关PoI的事件和接触的其它用户响应的请求。遇到一个用户接收请求的质问者进一步请求他的邻居们在同一个社区关于PoI作出回应。同时,每个用户接收请求响应与事件有关PoI影响一生中如果他有这样的事件。除了实现应用程序使用“环境敏感”社区和“contact-only”社区,我们实现两种基线的方法——“neighbor-all”(上界)用户接收请求从原始讯问者进一步请求他所有的邻居反应和“neighbor-none”(下限),用户不会进一步请求回应他的邻居。

图(13日)显示了查询成功率,这是成功的数量(即查询。,those queries which have at least one response) over the number of total queries (i.e., the number of PoI visits of all users), and Figure13 (b)显示了用户响应的平均数量为每个成功的查询。这是指平均数量的用户达成的查询查询正确的答案。这个指标演示了如何有效的社区建造,更高的平均数量的用户,更有效的社区结构。使用“环境敏感”社区达到更多用户正确的答案比使用“contact-only”查询的查询。这是因为环境敏感社区组织人基于潜在信息的影响,消除这些链接可能不会导致任何信息的影响。图13 (c)显示用户的平均数量是每个成功的查询请求。这个指标是测量成本。使用“环境敏感”社区带来更低的成本比使用“contact-only”社区。的平均降低成本约16.5%。这是因为contact-only群落结构涉及到大量的不相关的用户PoIs的查询,导致很多不必要的请求不能响应用户的查询。此外,“环境敏感”的查询请求成本接近下限比上界。

此外,我们观察到查询成功率很低。这不是一个指示群落结构的质量和社区对性能的影响。相反,这是因为用户移动到特定PoIs,可能很少遇到那些PoIs信息相同。如果更多的用户可以响应查询,可以改善性能。类似事件共享应用程序,没有日常性能的比较。总之,上下文感知社区事件查询有效的查询响应和高效的查询请求的成本。

7.3。更多的讨论结果

在这两个应用程序,使用上下文感知社区结构的性能比使用contact-only社区结构。事件转发的削减成本或查询请求成本这些应用程序验证我们的直觉6使用上下文感知社区结构的应用程序将会降低通信开销比使用纯contact-based群落结构由于使用影响较小和较社区构建图表。另一方面,因为超过80%的联系人UIM数据集不能导致信息影响的讨论部分6社区,环境敏感的优势尚未完全显现。实际上,使用上下文感知社区结构的性能可能更好更多的常规移动模式,如重复每天的机动性这可能导致重大影响和导致更高的相关性在社区内的信息。例如,基于移动概要图2,让我们添加流动的艾玛,她访问图书馆从下午5:30到6:30,遇到克里斯和戴夫在7点。假设艾玛一生有影响小时,所以她可以影响图书馆事件克里斯和戴夫在7点。然后,当克里斯遇到爱丽丝下午七点半,他可以进一步影响图书馆爱丽丝事件。同样,大卫也会影响图书馆事件鲍勃当他们遇到晚上8点。为图书馆,存在两个社区:一个与艾玛,克里斯,爱丽丝和另一个成员艾玛,戴夫,鲍勃。如果这些移动模式重复每一天,那么这两个社区(即变得越来越稳定。,links inside communities become stronger), resulting in Chris usually influences the library events to Alice, while Dave usually influences the library events to Bob. But assume, at certain days, Bob occasionally encounters Chris right after encountering Dave. In this case, Bob only needs to be influenced by Dave within their community regarding the library. There is no need for Bob to be influenced again with the same library events by Chris, so the unnecessary cost is avoided.

8。结论

在本文中,我们首先将时间和空间上下文整合成用户接触构造图产生影响。我们有建造使用影响图的基本环境敏感的社区结构和发达算法更新发展的社区结构。我们的性能研究表明,环境敏感社会结构(即具有良好的社会属性。、高平均IPS,合理的平均社区规模,平均每PoI社区)。在进化过程中是一致的,也是有效的反映信息影响而被有效更新社区。我们进一步应用发展的社区结构两种类型的移动社交applications-event共享和查询事件。我们的评估结果表明,该上下文感知社区结构是有效的在这两个事件交付和查询响应,同时也有效的事件代理成本和查询请求成本。

符号

:	一个完整的子图的大小
:	链接权重阈值
:	链接部分
:	原始链接分数
:	误差阈值的链接部分
:	数量的链接更新
:	影响一生。

利益冲突

作者宣称没有利益冲突有关的出版。

承认

这部分工作是支持由NSF格兰特cns - 0915574。