英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
附录3：
社会网络中节点的演化多样性与链接预测
摘要—近来，社交网络的普及程度大增。 社交网络研究中的一个关键问题是网络演进分析，它假定社交网络中的所有自治节点遵循统一的演化机制。 但是，社交网络中的不同节点应该具有不同的演化机制来产生不同的边。 这被提出作为确保节点在本文中的进化多样性的基本思想。 我们的方法涉及通过从节点的角度引入现有的链接预测方法来识别产生不同边的微级节点进化。 我们还提出了边生成系数来评估边生成可以通过链接预测方法解释的程度。 为了量化节点的演化多样性，我们定义了不同的演化距离。 此外，还提出了一种基于节点演化分集的间接分析整个网络演化的多元节点自适应算法。 在不同的现实世界网络上进行的大量实验表明，引入节点的进化多样性对于分析网络演进非常重要并且有益。 不同节点自适应算法在精度和通用性方面优于其他最先进的链接预测算法。 节点演化多样性越大，其优势越明显。
关键词 - 链接预测，网络演进分析，节点演变多样性，社交网络
- 介绍
基于社交网络的服务，如微信，Twitter，LinkedIn和Facebook，为用户提供了新的有趣的方式来相互连接。 这些网络通常用图表来表示，其中节点代表个人（人，组织或其他社会实体），边代表社会关系和交往（友谊，合作或信息交流）[1]。 近年来，社会网络在各个领域取得了巨大的成功，从发现社区[2]到防止私人信息推理攻击[3]，从检测犯罪活动[4]到搜索个性化的有影响力的主题[5]。 社会网络演进分析致力于理解网络形成的驱动力，并且是一个长期存在的挑战[6]。 其实际应用方面包括病毒式营销[7]，个性化推荐[8]和社会动员[9]。 当假设社交网络的所有节点都是固定的时，网络的形成反映在不同节点之间的边生成。 这通常是由正常和不正常因素驱动的。 考虑到社会网络中存在的节点作为固定节点，社会网络演化分析的首要任务是在规则因素的基础上解释社会网络中存在边的生成，具有很大的应用价值。 例如，发现不能解释的边对于检测在线购物网站上的异常交易，识别虚假的银行交易记录以及在犯罪团伙中单独打电话很有用。
一些优秀的进化机制已被接受为解释边生成的主要驱动力，包括三元封闭[10]，优先依附[11]，同源[12]，互惠[13]和社会平衡[14]。 现有的社会网络演化分析方法主要基于上述一种或两种机制构建机理模型; 然后，通过将所选特征参数与真实世界的社交网络进行比较来判断其建模性能。 虽然这些方法已经取得了有价值的理论结果[15]，但它们仍然很难与现实世界的社交网络相关联，因为它们忽略了节点变化的多样性。 节点之间的边的生成可以看作是节点进化的结果。 作为自主个体，社交网络中的节点通常在各种驱动力的作用下发展以产生不同的边。 现有的一种或两种机制无法为社会网络中所有节点的演化提供完整的解释，这促使我们关注社交网络中节点的演化多样性。 在本文中，节点的演化多样性反映在我们的假设中，即社交网络中的不同节点可以采用不同的演化机制来产生不同的边。
为了阐明引入节点演化多样性的意义，一个简单的例子如图1所示。图1—1中的社交网络来源于六个人之间的友谊关系。 现有方法通常通过均匀机制解释图1—1中七个边的生成。 统一机制的假设忽略了节点的进化多样性，而不能足以匹配真实世界的社交网络。 一方面，从两个不对称节点产生边可以有不同的解释，并且应该从节点的角度来考虑。 从E和F的对称观点来看，边的（E,F）可以用三元闭包的结构来解释，表示个人在图1-1b中与现有朋友的朋友交朋友的倾向。 但是，边（A,D）可以用优先依恋的结构来解释，这种结构表示与图1-1a中A的角度已经处于中心位置的人交往的倾向；这很难从D的角度来解释。另一方面，不同个体之间的社会互动受到个体特征的严重影响，并且个体可以独立地遵循不同的进化机制来产生不同的边。 虽然边（A，B）和（A，D）由节点A生成，（A，B）的生成不能从像A的生成那样的角度来解释（A，D）的产生。 除了更好地理解社交网络演进的基本动机之外，节点的演进多样性的引入对于异常检测应用也是有用的。 例如，在线社交网站中的异常用户可以通过监控他们的进化异常来发现。
图1-1基于不同节点演变的社交网络演进分析的简单例证
据我们所知，这是第一次关注社交网络中节点进化多样性并开发新颖解决方案以解决与节点进化多样性有关的关键问题：（1）是否有一种有效的方式来描述一个节点的演变？ 我们如何测量和评估社交网络中节点的演化多样性？ （2）基于节点的演化多样性，我们如何确定一种更好地分析网络演化的可行方法？ 我们是否有可能将我们的分析与其他现有分析进行公平比较？
与节点演化分集有关的上述问题的关键是描述和识别节点演化过程中不同边的产生机制。 网络演进机制的大多数定义都是非常抽象的，如图1—1所示，对于大型社交网络来说，一个接一个地分析节点边的生成是无效的。 另一个值得注意的重要方面是对基于节点进化多样性的分析进行相当的评估。 因为不同的机制通常有不同的方式来产生边，所以没有综合的机制模型可以整合不同的机制在同一时间。 由于太多可能的特征参数，仅通过比较一些选定的参数与真实世界的社交网络来判断性能将是非常主观的。
上述问题提出了链接预测问题，其中使用网络中的一组观察链路来估计未观测链路的存在可能性。 网络演进分析的合理程度与其相应的链接预测算法的性能一致[16],[17],[18],[19]。 一方面，有效的链接预测算法可以为相应的网络演化机制提供有力的证据。 例如，常见的基于邻域的算法的有效性表明了三元闭包的重要性[20]。 链接预测算法可以提供一种间接的方式来描述和识别节点进化过程中的边生成，而不是获得明确的机制。 边生成与其对应的链接预测算法最好地预测边的存在的机制最一致。 另一方面，更好的网络进化分析应该转化为良好的链接预测算法。 例如，分层网络组织的先验假设可以直接应用于链接预测算法的设计[21]。 链接预测算法的评估标准也可以提供一种公平的方法来评估通过其派生算法分析网络演变。
在本文中，我们介绍现有的微观层面的链接预测方法，通过解释其边的几代来间接描述节点的演变。边生成系数（egc）被提出来评估从边节点的角度来看边可以通过链接预测算法来解释的程度。 根据egc，自适应链接预测算法（alp）针对每个边进行匹配。 为了量化节点固有的演化分集，我们定义了不同的演化距离（Ded）。为进一步研究节点进化多样性的意义，提出了基于节点进化多样性的网络进化间接分析的多元节点自适应算法（DNAA）进行链接预测。
本文的其余部分安排如下。第2节介绍链接预测方法的背景，并回顾有关社交网络分析的研究。第3节正式定义节点的演化多样性和与节点演化多样性有关的两个关键问题，分别在第4节和第5节中解决。第4节描述了如何评估客户社交网络中节点的演化多样性，包括如何应用不同的链接预测方法来描述和识别节点的演变。第5节介绍链接预测算法DNAA，它说明了节点进化多样性的重要性。 第6节讨论了节点进化多样性的基本原理。 另外，将DNAA与来自不同应用领域的各种数据集上的基线和最先进的链接预测算法进行比较。 还研究了动态参数和节点进化多样性在DNAA性能中的作用。 最后，第7节总结本文并简要探讨未来研究的方向。
- 相关工作
就我们所知，这是第一个提出量化方法来分析社交网络中节点的演化多样性的研究。 本研究包括两个相关的研究领域：链接预测和网络演化分析。
链接预测问题一直是一个长期的挑战。它在跨学科领域有着广泛的应用，包括发现社交网络的缺失部分[22]，并分别在在线社交网络和电子商务网站上推荐朋友和产品[23]。已经提出了各种链接预测算法来解决链接预测问题[24],[25],[26],[27],[28],[29],[30]。链接预测算法的主要过程是给每个链接分配一个似然分，并且所有的非观察链接都根据它们的分数排序，假设分数越高链接的存在可能性越高[24]。每个边的似然计算的定义是主密钥。 链接预测算法的主要类型如下：（1）基于相似性的算法：这些算法采用节点的基本属性来定义它们的相似性，如节点间存在许多共同的特征或拓扑结构[25]。 相似性计算过程可能很复杂或简单，对于某些网络可能效果不错，但对其他网络却不适用。（2）最大似然算法：这些算法预先假定网络结构的一些组织原则，并且优化它们的规则和参数以最大化观察结构的可能性。 此外，还要考虑网络的结构特征，例如分级组织[26]和社区结构[27]，也为设计最大似然算法提供了有用的信息和见解。 然而，即使设计良好的最大似然算法也只能在合理的时间内处理多达数千个节点的网络，并且肯定无法处理大型的在线社交网络[28]。（3）概率模型[29]，[30]：这些模型旨在从观测网络中抽象出潜在的结构。他们优化目标函数以建立一个最适合目标网络观测数据的参数模型。然后，通过条件概率来估计不存在的链路的存在概率。
大多数现有的分析社交网络演进的方法都侧重于构建机械模型。已经提出了各种机制模型来揭示社交网络令人印象深刻的统计特征的起源，例如常规网络[31]和随机网络[32]，此外还有瓦茨和斯特罗加茨关于小世界网络（WS）的开创性工作模型）[33]，以及巴拉巴西和阿尔伯特在无标度网络（BA模型）[34]。WS模型描述了一个事实，即大型网络中任何两个节点之间的平均路径可能相对较短[33]。BA模型有两个特点：网络规模随着时间的增长而增长，以及优先附着，因此已经高度连接的节点获得新链接的相对概率比例较大[34]。 刘等人。[35]提出了一个基于直观但现实的考虑的模型，即节点通过优惠和随机附件添加到网络中。 进一步，他们调查了随机故障和故意袭击对他们模型的影响。此外，已经提出了相当多的统计参数来揭示社交网络的结构特征，如度分布[36]，聚类系数[37]和平均距离[38]。评估机械模型性能的一种被广泛接受的方法是比较这种模型与真实世界社交网络在某些特定统计参数方面的相似性。
然而，即使对于一个给定的真实社交网络，也很难公平地评估不同机制模型的有效性。 由于统计特征太多，因此很难选择正确的统计特征。为了克服这个缺点，已经提出了基于链接预测方法的方法来分析社交网络的演变[16]，[17]，[18]，[19]。社交网络的演进涉及两个过程：节点的添加或删除，以及节点之间的边生成[39]。 链接预测方法和边生成都关注边变化，所以我们可以应用链接预测方法来描述边的生成。对于固定节点，当链接预测方法准确预测机械模型中的生成边时，可以说链接预测方法可以充分描述边的生成。 另外，机械模型中边的生成可以被看作是一种链接预测算法，它将链接预测和机械模型联系起来。 网络演进机制在理论上具有相应的链接预测算法[16]，[17]，[18]，[19]。通过估计相应链接预测算法的性能，可以间接描述社交网络的演变。Zhang等人[18]新引入了链接预测和可能性分析方法来测量复杂网络的多重进化机制，并分析了流行度和聚类在真实世界社交网络中的系数。
尽管基于链路预警的网络演进分析，词典提供了一种公平比较不同演化机制的有效方式，它仍然关注整个网络的宏观视角，与机械模型的构建类似。假定所有的边生代遵循一个或两个统一的演化机制，忽略节点的演化多样性。同一社交网络中的不同节点可能受到不同因素的激励，以生成与其他节点的链接。为了更真实地描述真实世界的社交网络，重要的是要考虑基于多种机制的节点的演化分集。此外，现有的链接预测算法都是从链路的角度来设计的，它忽略了链路节点的自主性。 然而，我们试图从微观层面的节点角度更新现有的链接预测方法; 然后，应用这些更新变化来描述和识别节点的演变。 为了公平调查引入节点演化分集的意义，提出了一种基于节点演化分集的链接预测算法来分析网络演化。
- 问题定义
表3-1总结了本文中常用的符号。本研究致力于解决一些问题有关节点进化多样性的问题，关键问题可分为问题一和问题二。问题一试图描述和识别一个节点的演变，而问题二则侧重于评估基于节点演化多样性分析整个网络演变的性能。
表3-1本文中常用的符号
全文共27422字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[15381]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
|
符号 |
说明 |
|
G |
未加权和无向图 |
|
V |
G的节点集 |
|
E |
G的边集 |
|
Epr |
探针组 |
|
Etr |
训练集 |
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
