无需感染时间信息的传播网络快速推断算法

现有的大多数传播网络推断方法需要节点的感染时间信息,但是在许多现实传播过程中,准确的感染时间信息往往是难以获得的。以准确、高效且无需感染时间信息的传播网络推断方法为目标,研究了如何仅利用多次传播过程结束时观测到的各节点的感染状态来推断节点间的影响关系和感染传播概率。为此,该方法首先利用节点感染状态间的互信息来量化它们之间的相互关联,找出可能的节点间影响关系。然后,构建以感染传播概率为变量的节点感染状态观测数据的对数似然函数,并采用期望最大化的方法最大化该对数似然函数并求解感染传播概率。实验结果表明,相较现有方法,该方法有效提高了传播网络推断的准确性,并且大幅缩短了算法运行所需时间。     

信息传播网络推断综述

信息的传播扩散可以建模为在潜在传播网络上发生的随机过程。由于在实际应用场景中，潜在的传播网络拓扑结构和清晰的传播过程往往是不可见的，因此根据观测到的传播结果，如节点感染时间、状态等信息，推断传播网络拓扑结构，对于分析与理解传播过程、跟踪传播路径以及预测未来传播事件起着重要作用。近年来，传播网络推断问题吸引了众多研究者的目光。文中对近年来的信息传播网络推断工作进行系统性的介绍和总结，为传播网络推断提供一个新视角。     

基于信息传播节点集的CTDN节点分类算法

针对连续时间动态网络的节点分类问题,根据实际网络信息传播特点定义信息传播节点集,改进网络表示学习的节点序列采样策略,并设计基于信息传播节点集的连续时间动态网络节点分类算法,通过网络表示学习方法生成的节点低维向量以及OpenNE框架内的LogicRegression分类器,获得连续时间动态网络的节点分类结果。实验结果表明,与CTDNE和STWalk算法相比,该算法在实验条件相同的情况下,网络表示学习结果的二维可视化效果更优且最终的网络节点分类精度更高。     

基于MRLT模型多关系社交网络影响力最大化研究

社交网络影响力最大化问题是基于特定的传播模型,在网络中寻找一组初始传播节点集合,通过其产生最终传播影响范围最大的一种最优化问题。已有的相关研究大多只是针对单关系社交网络,即在社交网络中只存在一种关系。但在现实中,社交网络的用户之间往往存在着多种关系,并且这多种关系共同影响着网络信息传播及其最终影响范围。在线性阈值模型的基础上,结合网络节点间存在的多种关系,提出MRLT传播模型来建模节点间的影响力传播过程,在此基础上提出基于反向可达集的MR-RRset算法,解决了传统影响力最大化问题研究过程中由于使用贪心算法所导致的计算性能较低的问题。最后通过在真实数据集上的实验对比,表明所提方法具有更好的影响力传播范围及较大的计算性能提升。     

基于互信息的适用于高维数据的因果推断算法

推断数据间存在的因果关系是很多科学领域中的一个基础问题。然而现在暂时还没有快速有效的方法对高维数据进行因果推断。为此,提出了一种基于互信息的适应于高维数据的因果推断算法,该算法采取将高维网络结构学习问题分解成每一个节点的因果网络结构学习问题的策略。在第一阶段,利用基于互信息的条件独立性测试算法寻找目标节点的父子节点;在第二阶段,利用一种混合的方向识别算法对目标节点与其父子节点之间的方向进行判别,所有节点迭代完后得到一个完整的因果网络。数据实验表明,该算法在高维数据的情况下要优于目前其他的算法。     

利用节点传播熵识别超网络重要节点

超网络中识别重要节点是一项基础且具有挑战性的重要课题，相关研究对进一步分析网络拓扑结构和功能特性具有广泛的应用价值。为了突破已有的重要节点识别方法评估的局限性，利用超图及信息熵理论，提出一种基于节点传播熵的超网络重要节点识别方法。该方法兼顾节点的局部和全局拓扑信息，利用节点聚集系数和邻居数目表征节点信息的局部传播影响，通过节点间最短路径和K壳中心性反映节点信息的全局传播影响，充分考虑节点自身及其邻域节点的影响，最终利用节点传播熵来表征节点在网络中的重要性。并通过单调性、鲁棒性以及SIR传播模型评价标准，在六个来自不同领域的真实网络上与其他方法进行比较，实验结果表明，该方法能够准确有效地识别网络中的重要节点。     

基于中心度的标签传播时间序列聚类方法

为了实现时间序列自动聚类,以及更为细致地描述时间序列之间的结构关系,引入社区发现方法来研究时间序列聚类.针对标签传播方法在标签传播过程中具有较强不确定性,以及算法对网络结构较为敏感等问题,提出一种基于中心度的标签传播时间序列聚类方法;通过构建时间序列网络空间结构,将每条时间序列看作一个节点,根据每个节点的中心度来得到标签更新顺序;计算节点对于每个簇的归属度,再利用节点的归属度和标签的传播实现节点的划分,从而实现时间序列聚类.所提方法通过分析时间序列之间的连接关系来发现其在欧氏空间的结构特征,进而实现空间结构的有效划分.实验结果表明,所提方法无需确定初始簇中心,能够有效划分人工数据网络和真实社会网络,在时间序列数据聚类中取得了良好的聚类效果.     

基于网络社团结构的节点传播影响力分析

识别社会关系网络中对传播过程影响力大的关键节点,对于理解并控制网络上的传播具有重要意义.文中提出了一种基于网络社团结构的节点影响力度量方法,基本思想是用与某个节点直接相连的社团的数目(称为该节点的VC值)来衡量该节点的传播能力.通过单源感染的SIR传播模型实验发现,在根据已有节点重要性度量指标进行排序后,用节点的VC值可进一步挖掘传播能力强的奇异节点.通过单源感染的SI传播模型的实验发现,在具有相同度值或K-壳值(KS)的节点中,以VC较高的节点作为感染源,感染速度更快且可获得更大的传播范围.     

一种基于多关系传播树的谣言检测方法

近年来,社交媒体为人们消费信息提供便利的同时,也逐渐成为谣言产生和传播的温床.为了降低谣言的危害性,谣言检测受到研究学者的广泛关注.近期研究主要基于博文内容和传播结构信息,利用深度学习模型进行谣言检测.但是,这些方法仅考虑传播过程中博文之间的显式交互关系,忽略了对潜在关系的建模,难以捕捉到丰富的传播结构特征.例如,在转发(或评论)的交互形式下,多个转发者(或评论者)之间往往也存在局部的隐式交互.针对该挑战,提出一种基于多关系传播树的谣言检测方法,建模博文之间的多种依赖关系,同时增强重要博文的影响力,以捕获更丰富的信息传播结构特征.具体地,基于文本内容和传播树结构建立异构图,使用多关系图卷积网络建模父子节点之间的层间依赖关系和兄弟节点之间的层内依赖关系,并利用源节点和关键传播节点建模重要博文在信息传播中的潜在影响力,从而学习一个更全面的特征向量表示,用于检测谣言.在3个公开的真实数据集上进行广泛的实验,结果表明该方法具有比其他基线方法更高的谣言检测性能.     

基于PageRank的在线社交网络消息传播模型

经典的消息传播模型没有充分考虑在线社交网络的复杂性以及网络节点间的拓扑结构差异。针对这种情况,提出一种基于PageRank的在线社交网络的消息传播模型P-SIR。该模型利用节点的PageRank值作为节点权威度并考虑在线社交网络传播机理,刻画不同类型节点随着时间变化的状态演化关系,反映消息传播过程受到网络拓扑结构和传播机理的影响。该模型还考虑在线社交网络中影响消息传播过程中的一些实际因素,动态指定节点的权威度以适应非均质网络,并考虑外部社会加强效应。采用3种不同类型的网络模拟消息传播过程,通过仿真实验验证P-SIR模型可以有效反映在线社交网络中的消息传播过程。     

基于重叠社区搜索的传播热点选择方法

随着社交网络的蓬勃发展,信息传播问题由于具有广泛的应用前景而受到广泛关注,影响力最大化问题是信息传播中的一个研究热点.它致力于在信息传播过程开始之前选取能够使预期影响力达到最大的节点作为信息传播的初始节点,并且多采用基于概率的模型,如独立级联模型等.然而,现有的影响力最大化解决方案大多认为信息传播过程是自动的,忽略了社交网站平台在信息传播过程中可以起到的作用.此外,基于概率的模型存在一些问题,如无法保障信息的有效传播、无法适应动态变化的网络结构等等.因此,本文提出了一种基于重叠社区搜索的传播热点选择方法,该方法通过迭代式推广模型根据用户行为反馈逐步选择影响力最大化节点,使社交网站平台在信息传播过程中充分发挥控制作用,并提出一种新型的基于重叠社区结构的方法来衡量节点影响力,根据这种衡量方式来选择传播热点.本文提出了解决该问题的两种精确算法,包括一种基本方法和一种优化方法,以及该问题的近似算法.并通过大量实验验证了精确及近似算法的效率和近似算法的准确率以及迭代式传播热点选择方法的有效性.     

网络演化中基于事件的节点影响力分析

社会影响力分析是社会网络研究领域的一个重要研究热点,目前大多数 的影响力分析都是针对静态网络的。针对网络演化提出了一种基于个体事件的影响力分析方法,首先改进了传统扩散模型以适用于网络演化,并对在扩散中表现出的事件进行了定义,然后基于其中的个体事件测量了社交指数和影响力指数来衡量节点影响力,从而挖掘出动态网络影响力最大化问题中的关键节点。实验分别计算了节点的两个指标并对得出的结果分别进行了分析,找出了影响力较大的重要节点,然后对两个指标的性能进行了对比,结果表明利用社交指数发掘的节点在扩散前期传播的效率更高,而遇到扩散瓶颈时利用影响力指数发掘的节点则可以更快地突破瓶颈期。     

基于协调博弈的交通拥塞传播临界值研究

为深入分析交通网络的拥塞扩散过程,得出交通拥塞传播的临界值,提出了交通拥塞传播的协调博弈模型。通过网络个体之间的协调博弈,从出行者面对拥塞的决策行为出发,描述了交通网络的拥塞扩散过程。通过网络邻居之间的行为传递,形成了交通网络的拥塞扩散模型,并利用概率母函数方法推导了交通拥塞扩散的临界条件。最后构建了交通通塞的仿真系统,并通过路网结构、节点度分布等参数对交通拥塞进行了仿真分析。仿真实验结果与解析分析结果一致,并能反映交通拥塞动态过程信息,结果表明交通拥塞扩散的临界条件关键在于拥塞节点对周边正常节点的影响力,当局部交通拥塞对周边节点的影响力达到一定程度时,可能导致大规模交通拥塞的出现。     

Distributed linear estimation over sensor networks

We consider a network of sensors in which each node may collect noisy linear measurements of some unknown parameter. In this context, we study a distributed consensus diffusion scheme that relies only on bidirectional communication among neighbour nodes (nodes that can communicate and exchange data), and allows every node to compute an estimate of the unknown parameter that asymptotically converges to the true parameter. At each time iteration, a measurement update and a spatial diffusion phase are performed across the network, and a local least-squares estimate is computed at each node. The proposed scheme allows one to consider networks with dynamically changing communication topology, and it is robust to unreliable communication links and failures in measuring nodes. We show that under suitable hypotheses all the local estimates converge to the true parameter value.     

基于社团结构的节点的影响力分析*

复杂网络中最具影响力节点的识别对网络动力学如加速信息的扩散或抑制流言的传播都具有重要影响意义。为了给节点影响力做出具体排序,在已有的各种最具影响力节点识别方法的基础上,提出了一种基于社团结构和k-shell节点法的节点影响力识别方法,基本思想为利用某个节点处于不同社团的邻居节点的ks值判断节点影响力（称为Nc值）——识别ks值相同的节点的不同影响力。并通过单感染源传染的SIR模型进行仿真,发现Nc值较高的节点不仅最终节点的影响范围较大,传播速度也快于其他节点。     

融合多元信息的多关系社交网络节点重要性研究

识别重要节点是社会网络分析领域的重要任务之一,也是理解复杂网络结构和动力学特性的有效方式,迄今发展起来的节点重要性分析框架主要面向单关系网络.多关系网络作为准确刻画现实世界复杂系统的典型建模形式,已成为当前网络科学领域研究的热点,但对于多关系网络的节点重要性研究尚缺乏系统性的研究成果.针对多关系社交网络节点重要性研究问题,通过构建有向多重网络模型和基于张量代数的数学框架对其进行建模和分析,将中心性、声望和传递性作为影响社交网络节点重要性的关键因素,提出了一种面向多关系社交网络的节点重要性度量指标,并针对其存在不足引入D-S(Dempster-Shafer)证据理论进行改进,进一步提出了IOMEC(in-degree out-degree multiplex evidential centrality)节点重要性度量方法.在4个真实网络上的实验结果表明:采取信息融合的方法可以有效消除多关系网络耦合信息和传递机制对节点重要性评测造成的影响,提出的IOMEC方法能够更准确地对节点重要性进行度量,并且具有较低的时间复杂度,在论证节点中心性和声望是衡量节点重要程度主要因素的同时,说明了综合考虑节点传递性的必要性.所做工作为多关系网络节点重要性研究提供新的思路方法的同时,进一步拓展了信息融合技术的应用场景.     

融入迁移限制与双层集合种群网络的传染病模型

本文在斑块环境下基于易感–感染–易感模型(SIS模型)研究了感染者迁移限制对传染病传播的影响,其中迁移限制用双层网络进行表示,并提出了双层集合种群动态网络.子种群(即斑块)用双层网络上的节点表示,双层网络上的链接分别代表易感节点斑块和感染节点斑块间的迁移路径,易感染和感染节点分别通过双层网络上的链接随机游走.并提出了两种反应扩散方程分别作为易感染与感染节点的微分方程,分别计算其数值解,以评估每个斑块(节点)的感染风险.研究表明:在双层网络中,迁移限制会降低感染节点密度,将感染节点限制在中心节点(度值最高的子种群)中.感染节点密度高度依赖于双层网络结构.     

Deterministic broadcasting time with partial knowledge of the network

We consider the time of deterministic broadcasting in networks whose nodes have limited knowledge of network topology. Each node v knows only the part of the network within knowledge radius r from it, i.e., it knows the graph induced by all nodes at distance at most r from v. Apart from that, each node knows the maximum degree Δ of the network. One node of the network, called the source, has a message which has to reach all other nodes. We adopt the widely studied communication model called the one-way model in which, in every round, each node can communicate with at most one neighbor, and in each pair of nodes communicating in a given round, one can only send a message while the other can only receive it. This is the weakest of all store-and-forward models for point-to-point networks, and hence our algorithms work for other models as well, in at most the same time.

We show trade-offs between knowledge radius and time of deterministic broadcasting, when the knowledge radius is small, i.e., when nodes are only aware of their close vicinity. While for knowledge radius 0, minimum broadcasting time is Θ(e), where e is the number of edges in the network, broadcasting can be usually completed faster for positive knowledge radius. Our main results concern knowledge radius 1. We develop fast broadcasting algorithms and analyze their execution time. We also prove lower bounds on broadcasting time, showing that our algorithms are close to optimal.     

融合多元影响力节点识别指标MPR的链接预测

多元网络通常是指节点之间存在多种维度链接关系的图结构.多元网络链接预测算法在构建相似度指标时,多数仅考虑单一维度网络的拓扑结构属性,未挖掘不同维度子网络之间存在的关联,影响链接预测的效果.针对该问题,提出一种基于多元全局节点影响力识别指标MPR的多元网络链接预测算法.通过定义一个多维度节点影响力排序指标MPR,度量多元网络空间中影响力较大的节点,并把影响力排名函数转化为潜在节点对之间的相似度得分,从而应用到多元网络链接预测场景中.在2个真实多元网络数据集上的实验结果表明,该算法的预测效果优于PR、EDC、ANC等对比算法,且具有较好的稳定性.     

异质信息网络中基于网络嵌入的影响力最大化

针对当前大部分影响力最大化算法忽略了异质信息网络包含多种节点类型和多种关系类型,且不同类型节点在原始空间无法直接度量的问题,提出了一种异质信息网络中基于网络嵌入的影响力最大化模型（influence maximization based on network embedding,IMNE）,用于选择初始扩散节点实现影响力最大化。该模型不仅可以在对异质信息网络进行编码的同时表征异质信息网络中潜在的信息,还可以捕获不同类型节点间影响力的不确定和复杂性。在3个真实数据集上的实验验证了IMNE算法的有效性。