以时域信息实现对自我为中心的社会网络的链接预测外文翻译资料

英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料

以时域信息实现对自我为中心的社会网络的链接预测

摘要：链接预测被认为是网络科学的中心问题，因为它要求呈现管理着网络的微动态机制。在此工作中，令我们感兴趣的是自我为中心的社会网络，也就是在社会关系中一个个体与其邻居的纯信息交互。由于结构信息十分薄弱，我们依赖另一种信息源来预测一个个体邻居间的链接关系：互动时机。我们界定了一些特征以便于获得各种不通的时间信息，并采用机器学习法将这些不同的特征结合起来，以提高预测的质量。我们通过在一个手机互动数据集上展示了这种时间法的有效性，从而明确了一些能证明其在这样情景中能够表现得更好的特征，尤其是互动的时域剖面和联系双方间的消逝时间。

1引言

近年来，组织网络已成为一种代表任何一种交互系统的普遍方式，范围从蛋白质相互作用到网上社会网络。这种趋势因为代表的趋简性被调整，结合储存和处理大规模的数据集的技术可能。但是在大多数情况下，观察者对组织网络仅由片面的认识，要实现对互动的全面筹划通常具有挑战性。在不同的领域中，都有大规模的数据收集活动举行，尤其是在生物网络和互联网绘图方面，但是收集大量的数据需要花费大量的时间和空间。除此项成本外，度量衡学上的问题可能会倾向于索引过程并中和数据的可靠性。说到社会数据，这一问题通常源于传统的不利于数据分析的数据收集方式，比如个人访谈。网上社会网络提供了能够获得更大的数据集的途径。然而，出于商业，技术或法律上的权限，数据提供方通常限制用户获取资源的途径。相似地，即使是像手机运营商这样的私人公司对社会系统的认识也很有限，因为他们只有自己客户的全面信息，而对客户与其他公司之间的联系一无所知。

分析组织网络中的局部结构是规避这些问题的可行方式。在社会学中，以自我为中心的社会网络已经被研究了很久，也有许多措施被采用以便于描述和理解特定节点辺的局部结构环境。最近，如何合理地在这文本中定义社会概念是一个关注的重点。本篇论文主要考虑以下问题：了解一个节点与其直接邻居间的互动，猜测这些邻居间是否存在链接，换句话说，一个人的朋友中有谁是有可能相互认识的。这是一个典型的链接预测问题，但是在这情况下，有关组织网络的结构信息是缺失的。因此，我们寻求叫做时域信息的其他资源来发现节点与其社会网络间的链接。

组织网络中的链接预测问题通常用于从网络观测结构角度和例子中推断哪些链接将来可能会发生。这可以作为一种基于学习特征的机械学习任务，并且这任务与一个节点出现的可能性相关。结构特征通常有这样的目的，如共同邻居的数量和击中时间等。在研究中，我们可以发现许多可行的度量方式。还有其他一些可行的特征，例如节点层面上的属性或互动层面上的属性。至于社会网络中的链接预测，阶级不平衡问题应该予以考虑：一个稀疏的组织网络暗示着比实际连接更多的成对节点，意味着增加预测的数量存在着分类错误的危机。为缓解这个严峻的问题，尤其是通过监督学习技术，用于链接预测类型的群组节点配对，我们作出了许多努力，进而降低不平衡。

相互作用力学也是一种宝贵的资源。例如，众所周知的是，交流的频率和时长可助于判断人际关系类型是属于家人，商业关系还是朋友。许多工作利用了这一点来达到相关的预测目的，或者通过预测从上一个互动开始的消逝时间来揭露在自我为中心社会网络中的存在链接。考虑到电话数据集是一种代表着两个使用者间存在着社会相互作用的链接，可能出现的情况是我们仅有特定节点中的互动网络的局部信息。这是以自我为中心社会网络的最小版本，因为它包括这个节点和它的直接邻居。由于可利用的结构信息很少，我们选择时域信息来排序一个中心节点的邻居间的配对。高水准的配对应该能代表同一社会圈中的节点，并且有相互交流的倾向。我们还旨在于指出特别有用于链接预测的时域特征。

我们从交互时机角度出发设计了一些特征，然后解决综合排名问题。每个特点都为我们提供了一种排名，该排名暗示了比较可能相互联结的邻居配对。类似地，我们将这些排名与一种管理框架结合，从这些特征中尽可能多地得到信息，以至于结果排名能高于最有可能联结的配对。首先，我们使用传统的归类方式，并显现其限制性，因为预测的数量无法根据我们的需要来确定。出于此，我们将学习排序体制用于大型网络中的链接预测。使用学习排序体制代替归类方法的好处在于我们可以通过排名的top-T配对准确预测T链接。

论文第二部分描述了正在试验当中的手机和短信数据集。第三部分展示了如何使用暂时性交互对这些数据进行链接预测，讨论了用于对比的协议评估和静态指标后，我们提供了一些旨在在自我节点的邻居中实现链接预测的时域特征，进而解释了如何运用这些特征来排序，高水准的配对更有可能联结。为了实现最精准的预测，归类和更好地学习排序技巧。第四部分提出了能结合以上排序的管理策略。

2数据集

2.1预处理

被检查的数据集是一个子进程中的通信集合，是一组针对欧洲手机服务提供商的匿名用户。 它包含在一个月内周围电话和在任何一对用户之间做出的短信数据集。 以后，我们要区分呼叫和短信，因为我们假设这些通信手段没有同一个人以同样目的使用。呼叫可以表示为四元组{source，destination，timestamp，duration}的列表。 具有null持续时间的呼叫对应到没有答复的电话，已经从数据集中过滤掉。 文本消息被存储作为三元组，{source，destination，timestamp}。

这种数据的通常网络表示包括将用户描述为节点以及两个用户之间至少存在一个交互作为一个链接。 这些链接可能是按照一定的方向分配，这取决于谁在呼叫/发短信谁。两节点i和j之间的互动（或者是呼叫或消息）总数和记录期将被称为该链接的权重w（i，j）。

我们对通信网络的社会群体感兴趣，删除不代表持久社会关系的电话和短信。我们只考虑双向链接的呼叫，也就是说在两个方向已经被激活的链接[19]。 除了此步骤，用户之间的交互被认为是无方向。 数据归结为1，241，865节点和1，514，490，链接 - 独特和呼叫或消息链接，对应于10，934，277电话和27，060，340预处理后的短信。

从现在开始，网络被视为一套孤立的自我网络，也就是说中央节点与其直接邻居之间的相互作用。 节点具有异构 ——对于电话和文字信息的分布度和重量，见图1。 众所周知，预测质量取决于中心的程度节点在[20]中加下划线。 通常，由于这样的原因，它对低度节点的影响不大，但缺乏信息。 因此，我们将节点组合在一起成为学位课程。学习将分别对这些集合中的每一个进行处理，以提高性能。

2.2自主网络特定城市分析

我们考虑一个场景，其中唯一可用的信息是对呼叫节点与其邻居的交互的时间（和持续时间），关于网络结构的信息很少。这些相互作用的时间模式在社会圈子中具有潜在的障碍，从而使我们能够预测邻里存在的联系的自我节点。以前的作品强调了阶级不平衡的联系的戏剧效应社交网络中的预测问题，特别是移动电话网络（[11，20]））。与网络中的链接相比，有更多的节点对，这使得预测及其评估变得棘手。 a的类别比例的典型数量级N个节点的网络为O（1/ N）。然而，在自我网络的情况下，类不平衡效应较少成为问题，因为k节点的邻居最多，具有k（k-1）/2链路在他们中间。缺乏结构性信息的直接后果是自我网络成为标准算法，例如基于常见的邻居，是无法预测两个节点之间的链接比纯粹的随机预测更好。

图1

3基于时间信息的预测

在本节中，我们介绍用于评估时间信息的协议提高自我节点邻居之间链路预测的质量。 基于这个目的，我们定义允许排列成对的节点的度量，其中排名最高的对是最有可能连接的。

3.1协议和预测评估

对于每个等级k，即自我节点的程度，我们将自我网络划分为三个，根据以下比例设置：学习集（60％），验证集（20％）和测试集（20％）。 如果一个集合中有N个自然，我们将N·k·（k-1）/2作为对邻居排列在自我网络的联合。 两个邻居之间存在或不存在链接在学习集中应该是已知的，并将在学习阶段使用协议，而整个过程的性能在测试集上进行评估。验证集将用于确定所讨论的预测方法的参数。

然后将该过程分为两部分，一个无监督的排名部分一个监督的排名汇总。在第一部分中，根据度量m对节点进行排序。选择m与a的存在概率相关联邻居之间的联系。我们还使用基于共识的策略，从基于度量的排名中获得排名。生产的各种排名的质量是通过测量顶层对和正常相关量的真假预测数，即精度（Pr），回忆（Rc）和F分数来评估。让我们提醒一下F分数定义为2.Pr.Rc/(Pr Rc)。在[21]的各行中，我们使用精确回忆曲线来可视化预测的表现。我们也绘制F分数作为函数预测数量，因为这个数量与真正的数量成比例给定数量的预测。然后我们将监督学习后的排名相结合，在各种学位课程上尽可能准确地获得预测的方法。

图2

3.2静态基准

质量评估是与依靠基础的基准进行比较的结构信息。为了使得比较尽可能公平，我们对排名指标进行了一些测试，并保持最有效的指标。 每一对邻居（i，j）的自我e，与度k（e）和总重量W（e），给出了一个得分s（i，j）以及权重w（e，i）和w（e，j），这是这里唯一可用的结构信息。静态基准指标是：

图2描绘了从电话网络的学习集随机抽取kge;10时的1000个自我值的。 可以看出，s1，s4,s5明显优于其他指标和精度，对于低回忆预测更好。这个观察代表使用其他样品和其他类时的情况。因此，被用作静态基准参考文献。

3.3使用时间信息的度量

我们的目标是从自我到邻里的时间交流模式中尽可能多地绘制信息。为此，我们定义的弱分类指标是相互补充的，因为它们使用不同类型的方法或不同的时间尺度。

3.3.1链接强度指标

第一种方法这样假定，如果e和i之间存在很强的联系，那么e和j之间有很强的联系,i和j更有可能连接。 一个简单的方法来衡量一种关系的强度是电话的总持续时间。 如果（e，i）是e和i之间的声母的总持续时间，那么我们将持续时间得分定义为

力量可以以其他方式来进行测量，例如使用关系的规律性。我们确实可以期待有人称他们的亲戚在很长时间内是不被需要的，但定期（例如每天或每周）内却是必要的。 我们把规律关系中的gamma;（e，i）定义为w（e，i）除以事件时间的Fano因子F（e，i）后的结果。 让我们回想一下，分布的Fano因子是指它的方差的比率。 更规则的信号的特征在于较低的F值，因此gamma;（e，i）的值更高。 对于gamma;（e，i）定义，我们要求至少有两个事件间时间序列（至少是相互作用）。 然后确定规律性得分如

在图3和4中，我们显示了与基准项比较时，分别获得持续时间和规律度量。注意精确度和回忆率的提高对于固定数量的预测是同样重要的。考虑到不同的学位课程，容易得出，在所有情况下，在k=12时，除了具有持续时间的，其值为低或甚至为负。 在里面对于规则性指标的情况，第一次预测的改进是壮观的迅速下降到可忽略的价值观。 考虑到持续时间，改进不是那么高，第一个预测仍然有显著的预测效果。

图3

图4

图5

3.3.2时间效应

根据一天，一周或一年的时间不同，人们使用手机的目的不同。 例如，同事之间更多的是在工作时间而不是周末打电话给对方。 因此，我们预计通话频率会为潜在的社会团体提供线索。这应该反映在时间特征上，如图5所示。

我们通过以下方式来实现这个想法。 我们将时间线T分成两组：时间戳T_A和T_B，并计算两个时期的互动次数定义一个维度权重向量，（w_A（e，i）；w _B（e，i））。 假设这对节点与中央自我以相似的方式进行交互更容易被连接，得分然后从这些权重向量的标量积计算出对（i，j）：

注意当T_A=T,T_B= empty;时，S_pr=S₅

在图6中，我们总结了与之相比的精度和回忆改进基准

获得了不同程度的课程，具有时间表在周末和周末之间划分。 它揭示了Ｓ_ＰＲ－１表现更好，高于基准，达到67％，69％，66％和100％的增长k =3，k =6，k =9和k =12。 请注意，获得最佳的改进在排名第一的对中，将用于我们在4.4节中开发的聚合。

当然，我们可以在更多的组中查找时间轴的修复分区精确定义的边界，甚至重叠的类别。 但是，我们不了了之，通过组合几种弱分类特征来获得良好的排名。

3.3.3经过时间的方法

图6

图7

　　参加社交活动时，个人的呼叫概率很高，例如，在几个参与者的短时间内召集了一个会议点。更一般来说，呼叫之间的经过时间可以表示在两个电话中涉及的用户之间的关系。这就是为什么具体的时间模式在电话网络中被发现的频率比预期的随机模式更高（见[22，23]）。 这种相关性出现在各种时间尺度上。 例如定义会议点可能会在几分钟内涉及几个电话，通过检查几个小时甚至几天的模式，可能会出现一周的时间。

为了解释这个机制，我们定义了一个排名得分，这个排名得分考虑到这样一个事实：i和e之间的相互作用发生在j和e产生相互作用的不久前或者不久后。 为了做到这一点，我们把这个成绩作为参数来定义函数：

在这个式子中t_k是一个介于e和k之间的交互时间戳变量，H是Heaviside函数。换句话说，每一对互动（e-i，e-j）发生在比d短的时间内，这就增加了序数对（i，j）的分数。 这个想法在图7中示意性地表示。注意当时，S_d=infin;=S₅。

图8显示出S_d=1h,S_d =24h以及S<sub

剩余内容已隐藏，支付完成后下载完整资料</sub

资料编号：[25979]，资料为PDF文档或Word文档，PDF文档可免费转换为Word