文摘

我们认为在一个社交网络社区检测问题。一个社交网络是由小的社区;也就是说,一个社会可以分割成不同的社会群体中,同一组的成员保持强大和密度比个人来自不同团体的社会关系。换句话说,人们在同一个社区大大相互依存的社会特征,表明群落结构可能会促进理解人类的相互作用以及个人的行为。我们发现社会群体在一个手机用户通过分析基于蓝牙网络遇到历史上从一个真实的流动数据集。我们的社区检测方法着重于设计相似性测量能体现用户之间社会关系的程度通过考虑人工交互的tempospatial方面,其次是聚类算法。我们还展示了两种评价方法的提出方案。第一种方法依赖于友情的自然属性,长寿,频率,人类遇到被认为和规律性的特点。第二个是movement-prediction-based方法用于验证用户之间的社会关系。评价结果表明,该方案可以实现高性能探测社会群落结构。

1。介绍

社会社区检测允许深刻调查社会实体之间的网络结构(1,2]。研究人类的组织网络可以使社会特性,影响个人行为的理解和网络节点之间的相互作用3]。

社交网络维持群落结构(4,5];也就是说,人类社会可以被划分为不同的社会群体,在社会团体内部的连接(在同一组人)之间的联系更耐用,密度比个人不同的团体之间的连接。同一社会群体成员往往有强烈的相互依赖程度。他们更频繁地互动和分享彼此相关的行为特征在社区一级(6]。揭幕以来人类社会的基本结构可以帮助理解个人行为以及人与人之间的互动,社区检测已成为一个有吸引力的研究问题。

强大的传感功能的移动电话已经成为大多数人的生活的一个组成部分。他们提供能够记录用户的上下文信息相关的日常活动。最近,研究人员已经能够利用手机的功能来跟踪个人行为和收集足够的数据进行分析。

已经有一些研究在社会结构检测7- - - - - -13]。然而,这些研究没有考虑社会相似性度量(7- - - - - -11]或只考虑社会联系用户的存在(12,13),而不是考虑到用户的社会关系的优势。尽管一些研究认为用户之间相似性度量(14- - - - - -16),他们的主要目标是解决全新的数据路由问题实现容忍延迟网络,专注于分布式社区检测。在这些作品中,由于依赖本地维护信息,每个节点可能获得不同的和部分社会结构,而不是获得全球同意社会群落结构使用tempospatial上下文。

社会社区检测,另一方面,在这个工作中,我们专注于设计的相似性度量,可以反映用户之间社会关系的强度通过考虑人工交互的tempospatial方面,其次是集群用户获得稳固的关系的社会群体。我们提出两个相似度量:encounter-rate-based相似(人)和接触时间相关性相似(ETCS)。这些指标是用来识别人类关系的程度通过检查过去的用户遇到。在人方法中,人类遇到的频率是用来获得社会亲密。在交易所交易方法中,遇到的时空因素都是用来评估的程度的社会关系。集群,谱算法和自组织映射(SOM)用于获取社会社区。

我们还建议使用两种评价方法对社区检测方案,灵感来自人际关系的性质。第一种方法是基于友谊,友谊如频率,利用自然特色的长寿和规律性。作为额外的评价方法,我们开发了一个人类移动预测模型嵌入社会结构从社区获得检测方案。预测精度反映了意义的社会因素(即。,the level of interdependence between users in social groups), which makes it a potential method to validate the proposed community detection schemes.

友好的评价方法,结果表明,提出的相似性度量,ETCS人队,可以实现更高的性能比eigenbehavior-based方法在频率方面,长寿和规律性。我们观察到ETCS优于别人当大小(一组内成员的数量)的社会群体很大。与大小,一小群人比其他方法可以获得更高的性能。根据movement-prediction-based结果评价方法,提出的方案采用两个相似指标也优于现有方案的预测精度。评估结果也表明,光谱比使用SOM聚类更有益的社区检测方案。

从流动性human-carried设备收集的数据集从现实生活中,我们为我们的工作中提取必要的上下文数据。Bluetooth-encounter描述人工交互记录被用于社会结构检测。运动prediction-based评价方法,手机网络跟踪,能够提供移动用户的位置信息,另外就业。

总结我们的主要贡献如下:(我)为了检测社会,两个社会相似性测量方案,提出了确定水平的社会人与人之间的亲密关系基于遇到历史。人类交互的Tempospatial方面被认为是,直接和间接人工交互被用来估计社会用户之间的相似性。(2)上下文数据的人工交互和运动从一个真实的流动数据集的分析。(3)友好评价方法被开发来验证提出的社会社区检测方案,这是植根于友谊的自然属性。长寿,频率,考虑到人工交互的规律特征。(iv)提出了一种运动预测模型作为一个额外的评价方法。提出人类移动预测模型使用从社区获得社会社区信息检测方案和预测精度表明社区检测方案的有效性。

本文的其余部分组织如下。部分2概述相关作品从现有研究和相似性度量方法。我们使用的数据集的描述节中给出3。节4,我们建议我们的社区发现方法。人类的移动预测模型应用于这个工作将在部分解释5。节6,介绍了评价方法,我们也呈现结果和讨论。最后,给出本文的结论部分7。

2。相关的工作

在本节中,我们首先讨论社会结构检测方法的概述和比较那些与我们现有的研究。然后,我们介绍了eigenbehavior-based相似性度量,将用于与我们的计划。

2.1。社会结构检测

在本部分中,我们目前现有的研究检测的组织网络,与我们的工作相关。我们也比较那些与我们的方法。

许多研究在社会结构检测是基于图的聚类,这是最常见的方法,发现社区结构7- - - - - -11]。在图clustering-based方法,网络是由一个图形,然后利用集群技术划分为社区。例如,作者在7)提出了一个分裂的图聚类方法。首先形成社交图,边界边,这是最有可能充当共同性连接,被获得独立社区。在[17),球等人开发了一个统计图聚类方法采用采用的算法。另外一个例子,阮et al。18)提出了一个图clustering-based方法检测和监控重叠社区结构在动态移动网络,网络拓扑的频繁变化。

这些研究与我们的不同,他们主要集中在graph-partitioning算法,而不是测量社会个体间亲密的程度。我们工作的主要目标是确定个人与社会关系的社会群体。注意,确定社会相似性是必要的为了有效地检测网络结构,从一个社区需要区别于另一个社区水平的基础上个体之间的社会关系。在本文中,我们使用网络用户的交互历史获得社会亲密。

有几项研究被认为是社会网络中的节点相似性的基础上,联系历史。例如,戴利和Haahr [12决定一个社会相似度和介数中心度规,他们使用为了检测节点属于同一个社区和探测节点可以方便不同社区之间的沟通。Hossmann et al。13)还研究了聚合的意义联系建立一个社交网络。他们考虑了观测遇到过去估计节点之间的社会关系。潘伟迪et al。19)动态网络社区检测问题进行了研究。为了检测一个时变的社区结构,考虑时期划分为更小的时间间隔。在每个时间间隔,一个临时的社会联系是假定存在如果两个用户在彼此的空间距离。然而,在这些研究只考虑指标的可用性(存在)之间的社会联系用户通过使用过去遇到的阈值条件,而不是代表用户之间社会关系的优势。此外,的目的(19)来捕获时变群落结构,因此他们认为每个时间间隔的空间距离构建社会链接,而不是考虑长期人工交互在我们的工作。

在[20.)、波士顿等人提出了一个算法检测社会团体基于蓝牙的痕迹。他们使用的频率和持续时间为了集团用户用户的会议。被定义为一组会议会议涉及到一组两个以上用户,设置的所有用户对成对会议在同一时间。通过小组会议决定,用户设置标识。然后,阈值条件用于删除的微不足道的集会议小组会议频率和持续时间有限,获取用户组。

这项工作与我们的不同之处在于,他们认为,社会团体可以发现只有通过小组会议。相反,在我们的工作,用户可以属于同一社会群体没有小组会议通过间接用户之间的交互。此外,我们工作的目的是找到独立社会团体(可能导致一个大的社会群体),在用户有比较强的社会关系,同时,在他们的研究中,一个用户可以属于很多小组根据用户参加小组会议。

研究中广泛使用真实流动痕迹分析人类的社交网络是eigenbehavior [21]。鹰和Pentland决定个人的关系(他/她可能属于社区)通过对比社会行为的距离(如蓝牙设备遇到的数量)的个人不同用户预定义的社区。然而,社会亲密测量eigenbehavior只采用简单的上下文数据。例如,他们只数的数量过去遇到的一个个体,而不是考虑特定用户,个人遇到;即,每个成对遇到没有被考虑。

尽管这些研究探索交互历史上相似度的方法,我们的方法相比,他们没有充分考虑使用人类遇到的潜力,以反映社会关系。注意,在接触的信息与特定的用户,和特定的时间位置的接触,可能会提供一个有意义的社会个体的描述。因此,考虑到这些上下文数据让我们增强社会用户之间相似性的评估。在我们的方案中,我们提出一个新的方法来评估个体间的社会关系的程度,考虑人类互动的时间和空间两方面。这些水平的社会亲密由加权相似度值。

有一些社区检测方案基于每个用户的本地信息(14- - - - - -16,22]。例如,回族等。14)开发分布式社区检测方案中单个节点检测到自己的当地社区。为了估计网络节点之间的关系,他们认为使用接触时间和接触的数量在过去,这是相关的熟悉和人际互动的规律特征。在[15],Bulut和西曼斯基提出了一个指标来评估一个网络节点的满足程度的动机以共享数据与另一个节点。这个指标是基于三个友谊的自然属性:长寿,频率,human-encounter历史上和规律性。李、吴(16]定义了两两个人之间的相似性度量工作遇到的频率、平均和总接触时间,会议时间之间的分离时期。威廉姆斯et al。22]研究了动态网络社区检测问题。基于以遇到图构造,每个节点集中在确定periodic-encounter社区(即。组,小组成员定期遇到彼此)。然后,在本地获得节点之间数据交换的机会以确定全球社区结构。

这些研究不同于我们的工作,每个节点只使用它在本地维护的信息来发现社会。因此,每个节点可获得不同的和部分社区结构取决于它的信息,而不是获得整个群落结构基于全局数据。尽管节点交换网络结构信息,它是困难和昂贵的实现在全球范围内达成社会群落结构和调整社会结构使用全局数据。我们还要注意,使用全局数据允许更多的上下文信息在人工交互。此外,这些研究并没有提供一个方法来显式地评估社区检测的性能。相反,他们使用数据包转发性能通过trace-driven模拟,通过社区检测精度需要推断。相比之下,为了评估社区检测的性能,我们建议使用两种方法,它是基于友谊和人类的自然属性流动性预测模型。尽我们所知,没有研究已经提出了分析方法,评估社区检测方案利用自然人机交互的特点,我们在这篇文章中,基于分析真实流动的痕迹。

2.2。Eigenbehavior-Based相似

为了有效地发现社会群体、社会个体之间的相似之处需要就。在这里,我们介绍一个现有的相似度测量方法称为eigenbehavior [21]。这种方法侧重于测量行为数据之间的距离。

鹰和Pentland [21)提出了一个基于行为的相似性度量社会个体之间的距离和一个用户在一个预定义的社区。通过测量,然后比较,个人之间的距离和不同的用户在不同的社区,他们推断社区人所属。在一个用户的社会,存在多个社区,如进入实验室的学生,高级实验室的学生,学生和商业。为每一个社区,作者形成一个矩阵24代表社区行为数据。的行数,,对应于社区中的用户的数量,每一个行向量对应于个人的行为数据的用户社区。24列代表一天24小时间隔,和每一个行向量由24元素。每个元素的值代表了用户遇到的平均数量21)在实验期间相应的每小时间隔。

在这篇文章中,没有考虑到社区。因此,整个社会被认为是为所有用户。用户之间的相似性得到使用主成分分析(PCA)的基础(23)技术。主成分分析被广泛用于识别数据中的模式。使用主成分分析,可以提取数据的一个简单但有意义的表示。这种转换是通过主成分的线性组合(从协方差矩阵的特征向量,获得数据),这样大部分的变化呈现在原始的数据可以被保留下来。为了比较个人之间的行为数据来衡量他们的相似之处,主成分分析技术是用来描述社会的行为的数据。更具体地说,个人之间的社会距离决定,认定每个人没有任何先验知识对对方的社会背景。而不是构建一个不同行为矩阵为每个社区,只有一个矩阵米通过H成立代表所有用户,在哪里 =用户和的数量是每小时间隔的数量在当前的计划。考虑到向量是社会的平均行为和是行为向量的人吗j个体行为的偏差,将意味着行为 。然后,基于一组构造协方差矩阵(21]: 在哪里 。在这里,主成分的集合 (定义为eigenbehaviors)来源于这个行为的协方差矩阵。基于这些eigenbehaviors,一个人的行为可以通过下面的变换重建: 为 。一般来说,对于这个PCA-based方法,一个较小的数量h,在那里 ,对应的eigenbehaviorsh最大特征值足以代表用户(23]。之后,重建权向量的人j可以形成: 。与鹰和Pentland [21),以确定用户之间的社会距离,重建体重之间的欧几里得距离向量采用: 在哪里 用户之间的社会距离吗j和米,和是重建权重向量的用户j和米分别在社会。用户之间的相似度被认为是距离的倒数,可以推断出从距离使用常见的转换技术,如高斯内核(24]。

3所示。数据集

在本文中,我们使用麻省理工学院现实挖掘数据集(25]。这个真实的数据集由蓝牙距离痕迹,发射塔日志,和通信和移动应用程序日志,聚集来自90多个human-carried设备在2004年学年的一部分。参加实验的人来自麻省理工学院,包括媒体实验室成员和附近的斯隆商学院学生。因为他们在同一个学术研究所与相关位置,它们之间可能有很多社会关系,从而暗示社会参与者之间的群落结构。

参与这个实验给出了蓝牙手机软件预装日志。为了捕捉人类的相互作用,这些手机扫描周围环境每五分钟和记录他们的邻近的蓝牙设备列表对应的时间戳。因为用户可能手机几乎所有的时间在这项研究中,一个蓝牙跟踪可以代表人类的接触。每一次蓝牙移动设备之间的距离日志记录,这是假定为持有人之间的接触。此外,因为真实的会议可以持续更长的时间比蓝牙扫描的间隔,值得注意的是,一次会议之间的用户可能不是相同的遭遇。在我们的范围,一个会议的用户连续被认定为一系列基于蓝牙遇到它们之间。由于蓝牙扫描间隔五分钟,五分钟,如果两个人联系记录为两个邻近的事件。因此,每个接近事件被认为是用户之间的联系(相当于2.5分钟3]。

除了录音蓝牙用户之间的交互,这个数据集还包含发射塔痕迹,描述用户的动作。在蜂窝网络中,移动电话服务可用时,它位于基站的覆盖范围内。一般来说,这将是与最近的发射塔(最强信号)从它的当前位置。基于自然的个人行为我们观察到,移动用户将通过一天多个职位,和他/她的连接细胞相应地变化。每次设备执行一个新的协会发射塔,细胞标识符和各自的时间戳记录。因此,这些痕迹可以指示符号位置,每个对应的覆盖发射塔,贴上一个惟一的ID。考虑到基站的范围大约是几百米在城市地区,使用这些痕迹可以帮助跟踪用户活动的决议。

在麻省理工学院现实数据集,总共有106用户(有95用户实际数据)。对于社交网络的一个更好的表示,我们选择的用户组可以提供有用的数据在我们的分析。首先,正如eigenbehavior研究[21),在这个工作我们只考虑研究生痕迹的数据,大部分的参与者。一些参与者提供任何数据或一个非常小的数据量。因此,我们需要选择用户合理的数据量可以表示他/她的流动性。图1显示了用户在麻省理工学院获得的统计数据。如图1(一),有29个用户不到1000 Bluetooth-encounter痕迹在整个时期(平均值是4446)。同样,24用户不到10000发射塔如图痕迹1 (b)(平均:29781)和30个用户都参与不到60天,如图1 (c)(意思是:122)。基于图的观察1,我们认为这三个阈值选择用户和获得58个用户的集合。然后,我们确定所选用户的重叠期参与实验。图2显示了58个用户的参与时间。为了确保所选用户的分析,从9月23日,2004年12月7日,2004年,被认为是(总共54个工作日)。选择期间,我们还指出,一些用户的移动性数据不可用最有可能由于设备问题或偶尔的不活动的用户。因此,我们排除额外的15个用户,没有蓝牙遇到记录了20多天。最后,我们获得了43个用户进行分析。

图3介绍了蓝牙的数量的分布选择用户收集的数据在重叠的时间段。根据我们的观察,人类社会模式是依赖于时间。在工作时间,特别是从上午9点到18:00在工作日,日常行为往往是比在其他时间更普通。此外,我们可以看到在图3,工作日数据占大部分的人工交互。它也表明,大多数可用的交互发生在正常办公时间从上午9点到18:00。参与者来自相同的教育组织的事实可以解释为什么记录交互都集中在这些特定的时期。根据观察,在这个工作中,我们重点研究获得的数据在工作日,从上午9点到18:00。

4所示。社会社区检测

在本节中,我们提出新的方案,社会分割成更小的组,中移动用户有很强的社会团体内部的关系。该计划包括确定用户之间的相似性,紧随其后的是集群。

第一步是衡量社会移动用户之间的相似性。根据遇到的历史,反映了个体之间的交互,他们的亲密程度估计。因为这些社会相似性将被用作输入的聚类算法,它们的值需要度量理性,以确保我们的分析方案的最终结果。

与现有的研究依赖于简单的上下文(12,13,19,21)或本地维护的数据(14- - - - - -16,22),我们认为长期全球数据的人工交互设计相似性度量,利用更多的上下文信息,发现了在全球范围内达成社会群落结构。具体地说,谁与谁的信息和时间这些联系人的位置是用来估计社会相似性用户。此外,提出了相似性度量是基于间接人工交互以及直接的人工交互。

我们第一次呈现encounter-rate-based相似(人),然后描述遇到时间相关性相似(ETCS)。在人,接触的频率是直接用于估计两个特定用户之间社会关系的强度。在交易所交易,遇到的时空因素被认为是使用与时间相关性矩阵(矩阵等),其中包含所有用户的信息社会。此外,在交易所交易,两个特定用户之间的社会亲密是由他们与社会其他成员的互动。因此,比例可以被认为是一种间接关系的相似性度量。

社会亲密的评估后,执行聚类分区human-carried节点的社会到社会群体,在同一组的成员保持密切关系。社会团体内部的成员应该有亲密的交互属性(例如,高的规律性和持久的会议时间),以及相关的行为(例如,相互依存的运动模式)。这些特征可以用于评估阶段验证提出方法。

4.1。相似度测量

以下4.4.1。Encounter-Rate-Based相似(人)

在这种方法中,我们估计基于human-encounter率相似。在现实中,常常相见的人倾向于有一个强大的社会联系;因此,高接触率表明,这些用户有更亲密的关系。因此,我们确定成对相似性两个人使用它们之间的接触率: 在哪里 之间的接触率是用户j和米的比例(人的次数j遇到米重叠的天数),。

根据我们的观察,人类遇到的获得率是不对称的。在许多情况下的值 和 是不一样的。最可能的原因是不对称通信链接和用户之间不同的蓝牙日志记录的时间。方便的使用遇到率值的相似性度量,这是进一步的社会结构的输入检测方案,执行标准化这些值。我们使用特性的扩展将成对遇到率值区间内。然后,两两之间的相似度j和米是由两个值的平均值, 和 。如上所述,人的价值更高的指标表明用户进一步两两之间的关系。

4.1.2。遇到时间相关性相似(ETCS)

现在,我们引入一个新的相似性度量方法,它是基于一个遇到矩阵,代表两个成对人类遇到的时间和空间方面。

人队的方法试图估计社会用户采用两两之间的亲密接触。然而,它只考虑接触,而不是考虑那些遇到发生的时间;因此,不利用时间相关。潜在的,嵌入时间和空间两方面可以有效地确定人际关系的水平。

我们首先创建接触时间相关性矩阵(矩阵等)中的所有用户的社会。重叠的时期划分为许多不同的天。为了方便识别的人类互动的因素,每一个白天的时间分为更小的间隔。我们定义在一天的时间间隔。更具体地说,鉴于日常关注包含大多数人类交互的时期,白天是分成大小相等的时间间隔。正如节中提到的3,我们只考虑白天从上午9点到18:00,九个小时。如果我们选择一个小时的时间间隔,在每一天 时间间隔(例如,时间间隔1是上午9点到10点,时间间隔2是10点到11点,等等)。让T的天数在重叠的时期,几乎所有的用户都是活跃的。在那之后,从用户和天,我们构建通过 矩阵表示遇到用户之间重叠的每一个时间间隔期间。每一个行对应一个用户。另一方面,社会中的每个个体也与一块有关 连续列和列块形成后的顺序从1到用户。在每一个街区,一列对应于一个时间间隔一天重叠期间。

矩阵的一个元素显示了两个人之间的两两相遇。within-block索引列表明颞接触的位置,从时间间隔1天1开始,然后按照实际时间间隔的顺序一天的。我们可以看到在示例矩阵表1,第一块 列对应于用户1。我们可以看到,它开始索引为1和索引作为结束,这表明两个时间位置重叠的时期:时间间隔1天1和时间间隔的一天的,分别。例如,列索引2与用户1在时间间隔2天1,和,因此,矩阵元素是用户的次数遇到用户1在重叠的时间间隔2天1期。

我们从这等矩阵,确定用户的社会亲密。可以观察到的样本矩阵,一个行向量的用户j,这是表示,代表之间的接触j和社会的每一个其他用户(如用户2的行向量, 代表用户的接触与每个用户从1到2)。因此,我们注意到,它可能是有用的,以确定用户之间的相似性我和j通过比较他们的代表向量之间的所有交互描述整个社会和每个人。

应该强调,当我们确定用户之间的亲密关系我和j通过比较行向量和用户之间的直接交互和可能不会盈利。如果他们见面很多次,与用户相关的向量元素(对应列块在矩阵)代表的数量之间的接触和将满值非零,而相应的元素,显示了次用户遇到自己,仍将是零。因此,很明显,两个个体之间的直接接触的数量不是有助于获得它们之间的相似性。只有他们的交互与社会中其他成员将被用来衡量社会亲密。因此,指标可以被看作是一种间接的关系的方法。

我们的目标是评估社会人与人之间的亲密关系通过测量他们的社会互动的距离向量。构造等检查用户之间的关系矩阵是有前途的。然而,总的来说,人类之间的交互用户不可用在每一个时间间隔长重叠期间,和,因此,他们遇到的数据将会缺席(由元素与零矩阵)。因此,欧几里得基于距离的方法不适合决定用户之间的相似性,因为很有可能,矩阵包含稀疏数据。因此,我们测量了基于余弦相似度社会人与人之间的亲密关系,这是有效的稀疏数据,因为它将忽略coabsences的计算(26]。等的矩阵,我们计算出社会个体间相似度如下: 在哪里 是用户之间的相似性和和和的行向量和,分别。

4.2。聚类方法

确定社会相似性个人之后,下一步是揭露社会的结构。通过使用聚类算法,移动用户划分为若干个社会群体。在本文中,我们考虑谱聚类和自组织映射。

4.2.1。准备谱聚类

谱聚类(24)是一个简单的和有效的算法,它往往比传统的聚类方法。此外,这种基于方法可以转换成对相似性或距离社区网络节点之间的连接。

首先,邻接矩阵中元素代表了当地社区形成人与人之间的相似之处。这个过程相似性或距离映射到社区网络节点之间的关系。拟议中的相似性度量用户之间转变成邻接矩阵的元素。

在eigenbehavior-based方法的情况下,我们使用的高斯核函数24)获得邻接矩阵元素从用户行为之间的距离:

矩阵元素值0表明用户(除之间没有联系 ,),而1演示了相似性最高的价值。

以防encounter-rate-based和接触时间相关性相似方法,我们直接形成以来的邻接矩阵提出了相似之处能代表当地社区的关系,和他们的价值观已经在一个合适的时间间隔。

邻接矩阵的基础上,我们构建了一个使用对称拉普拉斯算子矩阵归一化技术(27]。然后,计算拉普拉斯算子矩阵的特征向量的集合。在集群用户之前k组,我们代表用户在一个低维空间,,这是由第一k特征向量(特征向量对应k最小特征值)。最后一步是使用则算法在数据空间中,每一行对应一个人在社会上,然后我们获得社会群体。因为不同的初始化可能产生不同的结果,我们执行则算法多次,然后选择最小化的结果的总结within-cluster point-to-centroid距离。具体来说,得到聚类结果,让集群的数据点集在k集群,让代表它的重心。然后,最小化损失函数的结果是选择, , 。

4.2.2。自组织映射

还在这篇文章中,我们考虑一个自组织映射(SOM)。SOM方法能够发现集群通过无监督培训过程(28]。

从技术上讲,SOM是一个人工神经网络。SOM网络仅仅是由两层组成:输入层(训练数据)和输出层。下文中,神经将引用映射到输出层的SOM。在SOM神经的典型拓扑映射网格。输出层中的每个神经元完全连接到输入层中的每个节点。输入层节点的数目是一样的尺寸输入数据的实例。SOM,每个神经元有一个相关联的空间位置和权重向量,相同的维度作为输入向量。

SOM的训练过程进行多次迭代。首先,每个神经元的权向量随机初始化。在每个迭代训练,样本从输入数据集是任意选择的。之后,输入样本和神经元之间的距离(由权向量表示)地图计算。有许多技术距离测量,欧几里得距离是最广泛用于此操作。然后,最佳匹配单元,一个神经元的权向量是接近当前的输入样本,确定。接下来,获胜者确定网格的空间邻居神经元将不得不调整自己的权向量。

在这里,之前SOM的适应过程,我们描述训练参数。鉴于目前获胜神经元,b周边,k,参数内核,即社区集中在获胜神经元,反映了之间的距离的影响k和b的训练速度k。在迭代t,它是计算如下: 在哪里,的坐标和在地图上,分别随时间减少。另一个参数是、学习速率也随时间下降。

在适应步骤,每个神经元在获胜者和邻国更新自己的权向量如下: 在哪里是输入样本当前迭代中。

基于(8),显然,获胜神经元会最大的适应速度。反复,对每个输入向量,确定获胜神经元;那么它和附近的邻居更新他们的权重向量,根据上述过程,直到算法是收敛的。

为了确定集群输入数据,大量的神经元网络中可以选择等于预定数量的集群。这个选择是可行的在我们的方案中,因为有有限数量的输入样本(43个用户)。SOM的分别,每个神经元输出层成为集群中心。训练阶段后,样本数据集将映射到集群中心是靠近它的地方。

我们选择相似性度量作为SOM聚类的输入数据。自SOM使用欧氏距离,接触时间相关性可能不是最合适的人选。因此,我们使用encounter-rate-based相似性聚类算法作为输入。在这里,每个encounter-rate-based向量代表个体与整个社会的相互作用。更具体地说,每个用户都由一个表示米维向量(在我们的方案中, ),向量组件之间的接触率,人与社会的其他成员。因此,通过应用SOM,我们旨在揭示用户通过比较他们的交互与他人之间的关系,类似于交易所交易的基于交互的方式。

5。人类迁移预测基于社会群体

在发现社区结构,我们使用产生的社会群体来预测人类的机动性。在本部分中,首先,我们将解释我们如何处理的原始痕迹提取有意义的迁移数据。之后,该预测模型将嵌入上下文特征从social-group-mates推断出给定用户的位置。人类流动预测精度将被用来验证我们提出的社会社区检测方案。

5.1。位置提取

指出移动用户的位置,麻省理工学院现实挖掘数据集提供蜂窝网络的移动数据。痕迹记录历史的发射塔IDs与电话每次它改变了发射塔。我们使用符号位置,对应相关的发射塔在特定的时间。

在本文中,我们感兴趣的是预测人体运动模式在白天期间周一至周五09:00 - 18:00,类似于社会结构检测阶段。基于原始发射塔日志,我们可以确定的时期human-carried设备被连接到一个特定的发射塔。然而,由于人体运动和信号衰落的本质,一个电话的时间连接到发射塔是不稳定的。在某些情况下,一个电话在一个细胞呆很长时间,虽然还有很多其他的情况下,移动设备只有与细胞在很短时间内,迅速切换到其他细胞。因此,通过使用原始信息,很难确定准确位置的用户建模为目的的人类活动。

为了使用适当的位置数据,我们白天时间分割成更小的,大小相同的时段,适合捕捉一般流动性。时间从上午9点到18:00,如果我们设置时间段长度30分钟,然后我们会有18个时间槽,在每一天。在一个时间段,电话可能切换到不同的基站。在这项研究中,移动用户的位置在一个给定时间段的发射塔被认为是最大的时间占时间槽。我们也表示阈值比率值提取的位置。在一个时间段,一个设备的时期是与最大的时间(即位置。需要超过细胞ID);否则,移动用户的位置被认为是未定义的。在这篇文章中,是0.3。注意,并不是每个人都参加了实验在一定时间;那就是,他们中的一些人可能关掉自己的手机。也有可能移动设备可能会收到没有手机信号。移动用户的位置在这些情况下定义和设置为0。

根据这个过程,我们得到每个移动用户的位置在社会的特定时间指数。颞位置可以描述一天一天的时间段。提取的时间和空间位置的用户被用作人类的上下文数据移动预测模型。

5.2。预测模型

我们的动机社会结构检测是了解个体的行为以及人工交互。基于社会团体发现通过社区检测方案,可以更好地理解人类行为喜欢运动。一般来说,有许多上下文特性影响现实生活中的人类活动(29日]。除了嵌入时间和空间因素的潜在流动性预测(30.),人们可以通过社会关系反映的运动。我们可以推断出一个人的运动模式通过使用上下文信息在他/她有一个强大的社会联系。在一个特定的时间,如果提供的位置与用户密切相关的人,然后,基于这些信息,我们可以预测用户的行踪。例如,周一从10点到10点半,如果所有social-group-mates给定用户的会议室,那么很有可能,用户也在周一的会议。

另一方面,人类流动预测社会社区可以是一个有用的评估工具检测。不同的社会社区检测方案导致不同的社区结构。如果用户的位置预测最为准确的基础上获得的社会群体社区检测算法,算法可以被认为是最合适的一个中提出的方法。因此,运动预测精度可以使用作为社会结构的验证方法检测方案。

在本文中,我们考虑使用朴素贝叶斯人力流动预测。因为预测人体运动的目标是评估获得的社会因素(社会结构获得通过使用方案中描述的部分4),我们使用最大似然估计方法由于其简单性和有效性。如表所示2预测给定用户的位置,我们考虑时间因素,包括星期和时间槽。我们对于社会因素,利用位置信息从social-group-mates给定用户预测他/她的位置。例如,如果用户属于一组五人,那么他/她的四个队友的位置将被使用。在一些特殊的情况下从我们的社会社区检测方案,一组由只有一个用户,社会因素将被忽略。考虑到上下文变量中描述表2,用户可以确定的预测位置如下: 在哪里 上下文变量的输入属性吗 ,是一个元素的集合可能值的(给定用户的位置)。

我们随机选择的一部分数据作为训练集,使用测试集验证预测模型。在我们的模型中,我们选择的培训/测试数据比8:2,这意味着数据来自38个随机选择的天中被利用的训练步骤,和剩下的16天的数据是用来验证预测模型。由于各种各样的符号位置(基站),零观察问题可以发生在条件概率 ,最终以零值(即。,the situation where the location of a social-group-mate never appears in the training set). To avoid this problem, the conditional probability is calculated following the Laplace smoothing technique [31日]: 在哪里k可能的值的总数吗。

一个剩余的问题对于我们的预测模型是未定义的存在位置的数据由于反感移动设备、网络连接问题,频繁的变化相关的细胞。象征性的位置0没有提供有用的信息对人类流动或交互;因此我们将上下文数据,其中包含这些毫无意义的地点。在一个特定的时间位置,如果任何用户或他/她的空间位置social-group-mates是未定义的,那么数据对应这时间被排除在我们的预测模型。尽管验证数据的数量可能会减少,我们打算确保所有输入和输出上下文变量的意义。

6。评价结果与讨论

在本节中,我们提出的性能分析,提出社区检测方案。我们首先描述了友好和运动prediction-based评价方法。然后,我们讨论评估结果。

6.1。友好的评价方法

友好的评价方法是根植于人类的自然特征的关系。我们的目标是评估社会社区检测方案通过测量程度的社会团体内部的社会成员之间的亲密关系。根据一项研究[15),人际关系可以反映三个基本属性,定义友谊;即亲密的两个人通过频率,公认的规律,和持续时间的交互。在我们工作的环境中,人类所代表的互动。因此,我们估计基于用户之间遇到历史的这些特征。我们定义三种友谊的度量属性。

图4演示了一个示例遇到两个人之间的历史。我们考虑的是频率第一友谊属性。我们两个人之间的频率指标定义为总数的比值之间的接触他们的总天数重叠的时期。人之间的两两频率指标我和j计算如下: 在哪里间遇到的总数吗和在重叠的时期天。

第二个指标是规律性。两个个体之间的交互是常规如果他们有段时间间隔(即保持一致。、小方差)。另一个考虑的时间尺度。给定相同的方差值,规模较大的两个个体之间的时间间隔的会议表明更常规的交互。因此,两个人之间的规律性可以测量的逆扩散指数(32)段时间间隔或均值的方差的比值这段时间间隔的重叠。这是 在哪里是连续两次会议之间的时间间隔的人吗和。

第三个特点,长寿,是证明了个体之间的交互的时间长度。一般来说,如果两个人之间的每一个会议持续很长一段时间,这表明他们有密切的关系。我们长寿的度量定义为两个人之间的会议活动的平均时间长度: 在哪里会晤的人的总数吗我和j。回想一下,一个会议的长度之间的人我和j是计算 分钟,这次会议是遇到相应的数量。

之后我们得到这些值频率、规律性和长寿,取平均值来表示指标的两两关系,以消除不对称的度量(例如,计算之间的区别和,如果它存在的话)。接下来,为每个三个指标,他们的价值观是规范化区间。鉴于社区检测方案Z分区的社会k社会团体、社会结构的整体性能检测方法计算如下: 整体关系值对应于上述的三个友谊指标之一;设置用户组吗, 代表用户之间两两关系价值和在集团,用户对组的数量吗。

6.2。Movement-Prediction-Based评价方法

节5,我们提出了一个预测模型,利用获得的结果从社会社区检测方案。预测模型的预测精度嵌入社会因素是用于评估指标。在这里,社会因素是提取获得的社会群体。机动性高预测精度表明social-group-mates强烈相关的行为,因此意味着一个更好的社区检测方案。

使用社区检测方案,社会划分为一个给定数量的社会群体。假设社会划分k社会群体。然后,平均预测精度基于社会社区检测方案(例如,encounters-rate-based与谱聚类相似度)决定如下: 在哪里是个体的数量( 在这篇文章中),是预测情况下用户的数量吗,是正确的预测用户的数量吗我。

自社会可以划分为不同的数据组,总体预测精度基于社会社区的社会因素检测方案计算如下: 在哪里和分别对应于最小和最大数量的群体社会划分。

预测模型采用朴素贝叶斯,我们认识到最可能位置的输出预测给定用户的位置。此外,我们还考虑考虑第二个最有可能的扩展位置。更具体地说,对于每一个预测,我们不仅考虑最高的位置预测概率,而且位置与第二高概率。然后,在这个扩展,如果真正的预测位置最可能相同或第二最有可能的地点,我们把它归类为一个正确的预测。因为这个修改可能提高当前的预测模型的能力,它可以为我们提供有用的验证movement-prediction-based社会社区检测评估。

6.3。结果与讨论

我们收集了结果使用该社区检测计划,人与谱聚类(encounter-rate-based相似),用SOM人,比例(接触时间相关性相似)其次是谱聚类。结果与eigenbehavior-based方法。

6.3.1。友好评价结果

图5显示了社区检测方案的评价结果使用友好指标、社会群体的数量被发现的地方4和10之间的不同。在每种情况下,整体的寿命值,频率和规律指标。

如图5人队和ETCS谱聚类节目表演比eigenbehavior-based方法检测亲密关系在社区一级。eigenbehavior-based指标超过了这两个相似度测量在每个友谊性质。eigenbehavior-based相似性测量只考虑用户的数量,每个人遇到的,而人队和ETCS嵌入一个更具体的上下文的用户接触他/她。上下文信息越少的性能低的原因是eigenbehavior-based相似方法,比别人。

我们可以看到在图5ETCS与谱聚类优于其他方法,当社会群体的数量少于8。例如,当社会群体的数量是5个,计划采用ETCS频率上涨35%,涨幅15%的规律性,在长寿和收益18%,比人与谱聚类方案。这表明采用人工交互的时间和空间方面都可以导致更好的估计他们的关系。然而,当社会群体数量的增加,这种优势消失,而人。请注意,如果社会群体数量的增加,社会群体的大小减少。在分析一个社会的43个用户,如果比八大,许多团体的大小减少到只有两个或三个成员。在这些情况下,直接从human-encounter率估计可以更有效率比ETCS揭示队友的关系。总体而言,当社会群体的规模很小,使用的人是很有用的指标。当社会群体的大小增加,使用比例指标更为有益。

它也值得讨论两种聚类算法的性能比较。一般来说,SOM能够准确地获取数据的集群结构提供了足够的数据量。回想一下,集群的数量我们的目标是确定可以高达10,而输入仅由43个实例。考虑到这些输入数据,需要在我们的方案中,SOM训练地图每个集群几个输入实例。由于数据的小型规模,培训过程中SOM可能无法返回精确映射。基于图的观察5,谱聚类显示了我们的社会社区检测方案更好的性能。

友好的评估结果,三种不同属性的关系表现出类似的趋势。不同的社会社区检测方案的性能类似在这三个案例。此外,友谊指标总体值增加时,社会分成更多的组。这表明三个属性的关系是高度相关的。此外,如果社会分成更多的社会群体,我们可以获得更高的友好亲密在社区一级。在这些情况下,每个社会群体包含的一些社会最亲密的朋友;同一组的成员通常是互相接触,因此有非常高度的社会亲密。

再。运动Prediction-Based评价结果

图6显示了朴素贝叶斯模型的预测精度的基础上,提出了四种不同情况下社会社区检测方案当社会群体的数量变化,从4 8、10。运动prediction-based评价,我们选择了十个不同的培训/测试集的数据集,然后收集在这十集的平均精度。

类似的模式之间的评价结果最可能的位置和可以观察到在图的第二个最可能的位置6。显然,当第二个最可能位置纳入预测输出,精度较高。

如图6,社会社区检测方案的性能与不同数量的变化k。当k的比例很小,谱聚类方案没有显示显著的性能,相对于其他方案。

注意,当社会划分为少量的社会群体,k,该集团可能很大(即大小。,there can be a number of individuals belonging to the same group). At a specific temporal position, some users’ locations can be undefined. Recall that when evaluating the movement of an individual, undefined location data about members of his/her social group are removed from our prediction model. Thus, for some cases, the amount of remaining contextual data may be small for the validation of human movement. Since with a largerk社会群体的大小变得更小,减少这个问题的影响,因此,评价是更可靠。在这些情况下,令人满意的验证数据量来评估社会因素预测模型的性能。因此,结果当社会划分为大量的组织会更好的说明我们的模型的能力。当社会群体的数量很大,可以观察到在图6,人与谱聚类和ETCS谱聚类方案显示movement-prediction-based性能高于其他方案。人队和比例指标比eigenbehavior-based相似性更好的测量社会亲密友谊性质和mobility-dependency标准。

我们也可以看到在图6,类似于友好评估,计划使用SOM显示低性能相比利用光谱。

图7显示个人流动预测准确率当移动用户的社会划分为10个社会群体。方案采用ETCS优于其他方法。社会因素的使用基于这个方案给了令人印象深刻的个人预测精度对于大多数用户的社会。

我们可以看到在图7,有一些情况下(当使用社会群体从人与SOM和eigenbehavior-based相似光谱聚类),个人预测准确率极低;即社会群体获得这两个方案不是有用的预测模型。此外,社会群体获得通过使用这些计划是不平衡的。例如,在社会群体中SOM计划的人,得到的一组用户的数量在15(远远大于组只包含一个或两个成员)。同样,使用eigenbehavior-based计划,有一个社会团体,由八个用户另一组只有一个用户;但它不是希望把社会分成小的分区。

运动prediction-based评价方法的结果表明,通过嵌入的社会因素,我们可以获得相当大的预测精度。此外,获得更大如果社会划分为大量的社会群体。这是因为如果一个社会群体的大小可以减少几个成员,然后小组成员往往是高度相关的运动决策。例如,当集群的数量是10,该计划将ETCS指标可以用来实现精度为50%时最可能的位置和65%以上包括第二个最有可能的位置。紧随其后的是人与谱聚类,有助于预测的准确性为45%和63%,分别在这两种情况。

可以观察到在图7、移动预测精度随用户的用户,因此这意味着不同的人可能有不同程度的行为相互依存。有些人似乎更少的社会依赖。使用social-group-mates上下文信息来预测他们的运动结果在有限的效率。另一方面,大多数用户倾向于高水平的社会依赖流动模式,他们的动作可以被嵌入的社会因素更容易预测。这些结果表明,社会因素是流动的潜在特性预测模型。

应该强调,在评价结果有不同的倾向之间的运动prediction-based和友好指标。与友谊性质的方法,即使大k使用比例指标仍然保留着比人更高的性能指标。结果表明,通过嵌入人工交互的时间因素测量社会人们之间的亲密行为依赖关系更好的反映在相似性度量。一般来说,如果两个人有一个丰富的两两相遇的历史,他们的关系可以反映在友谊的大值属性指标,但它可能并不总是意味着高之间的依赖他们的行为。作为一个例子,我们考虑这样一种情况:三个用户(a、B和C)属于同一组织,和他们每个人与其他社会关系。在我们的示例中,A和B是队友,而和C是私人朋友,但他们在不同的团队中工作。因为有a和C之间的个人关系,他们通常花时间与对方。因此,相对于A和B, A和C属性度量值可能会有更高的友谊。事实上,A和B是社会密切(来自同一个团队)意味着他们有相关的日常工作程序。因此,尽管这两个社会朋友,A和B,在友好度量值可能小于两个人朋友,A和C,行为依赖的程度(例如,运动)A和B之间可能是更高的。相似度测量,研究人工交互考虑时间和空间两方面将会有效地检测那些强烈的社会群体的成员相互依赖的运动模式。

7所示。结论

在本文中,我们研究了社会网络结构关注社区检测问题。我们的目标是确定在人类社会中个体之间的社会团体。我们使用一个真实的流动数据集与人之间的交互由基于蓝牙的遭遇,以及人体运动数据来源于手机网络痕迹。这个上下文信息让我们检查社区内移动用户的社会。我们介绍的方法测量社会个体之间的相似性分析人类历史联系。通过应用社会社区检测方案,我们分区社会到社会群体的用户。我们还提出了评价方法,采用人们之间的友谊属性和流动性的依赖。

性能结果表明,比例和人比eigenbehavior-based相似性测量方法。友好的评价结果表明,人比ETCS当社会群体的规模很小。另一方面,ETCS方法给社会群体的大小增加时更好的性能。运动prediction-based标准,方案采用ETCS优于其他方法。我们还发现,基于谱算法比SOM在社会结构检测。

我们探讨了潜在的人工交互的使用时间和空间方面的相似性度量,特别是在确定行为依赖人。我们发现,一个社会的因素,人们彼此亲密的社会是一个有前途的上下文特征建模人类运动模式。社会评价结果还表明,分区到大量的社会群体增加个体间行为相互依存和友好亲密的程度在一个社会团体内部的水平。

根据提出的方案,我们可以确定用户的社会团体有密切关系和相互依存的社会特征,从而提高系统的理解人类社会的相互作用和行为。能够识别这些社会结构可以促进合作网络的进一步应用,如城市数据挖掘和类似的机会主义路由数据。

值得注意的是,在这工作一个封闭的社区,人们长期的关系和相似的社会背景被认为是。然而,社区的类型和大小可以影响的结果提出社区检测方案。作为一个未来的研究中,我们计划要考虑各种社区类型和大小及其影响的性能提出方案和相应的扩展计划。

的利益冲突

作者宣称没有利益冲突有关这篇文章的出版。

确认

这项研究受到了基础科学研究项目通过韩国国家研究基金会(NRF)由教育部(NRF - 2016 r1d1a3b03934617)。