重要节点发现算法在民航旅客社会网络中的应用研究

当前,民航旅客价值分析把每一个旅客当作彼此不相关联的实体,忽略了旅客间存在的关系。针对这种情况,提出从旅客间的相互影响角度出发,量化这种影响的强弱。基于PNR(Passenger Name Record)数据构建民航旅客社会网络,从系统科学、网络关系和互联网搜索这三个角度研究社会网络中节点重要性的评估算法,并把这三种算法应用在民航旅客社会网络中。最后,通过F-度量方法对这三种算法计算出的重要节点进行相似性比较。实验结果表明,该方法能够有效地得到民航旅客社会网络中的重要旅客。

加权社会网络中重要节点发现算法

从社会网络中发现重要节点是一个很有意义的研究问题,目前多数重要节点发现方法是基于不加权网络。由于在社会网络中,节点之间的关系具有强弱差异,社会网络本质上是一个加权网络。对于加权社会网络中的重要节点发现较少有研究。利用节点交互,提出了节点间关系强度的一种度量方法,该方法考虑了节点局部有向交互特征与全局交互特征。利用节点的行为特征定义了节点活跃度。采用关系强度作为边的权重,活跃度作为节点权重形成了加权社会网络。基于PageRank算法的思想,提出了两个改进算法,算法采用节点权值作为阻尼系数,在迭代式过程用边的权重代替了PageRank算法中的入边和。分别选择国内外具有代表性的2个社交网络上的数据集进行大量实验,并分别选择了不同的方法作为比较,实验结果表明改进算法能较好地发现加权社会网络中的重要节点。

面向目标体系网络的节点重要性排序方法

针对现有复杂网络节点重要性排序方法无法处理目标体系网络节点异质连边有向有权的难题,提出一种面向目标体系网络的节点重要性排序方法。利用K-shell算法计算网络节点的初始重要值,并在PageRank算法的节点重要性传递中考虑重要性分配趋强的特点和连边权重,提出K-shell和PageRank扩展(Extended K-shell and PageRank,EKSPR)算法,并给出EKSPR算法的收敛性证明,进行了作战仿真实验验证和算例对比分析。实验结果表明,EKSPR算法相对于K-shell算法和PageRank算法更适用于处理目标体系网络节点重要性排序,并且效率优于均值EKSPR算法。

恶意攻击背景下电力信息网络节点重要度评估

电力信息网络中攻击事件频发,关键节点遭受攻击的概率增大,为迅速确定关键节点,解决其故障问题,设计一种恶意攻击背景下的电力信息网络节点重要度评估方法。抽象处理电力信息网络,通过Prim算法与社团分区方法相结合的分区方法进行网络区域划分,再构建电力信息网络模型,进行电力信息网络的区间连锁故障建模,计算恶意攻击下连锁故障过程中电力信息网络的负荷损失。基于HITs算法设计网络节点重要度评估算法,实现节点重要度的评估。测试结果表明,设计方法对垃圾节点的识别抵御率始终高于94%,证明该方法在实践中表现良好。

基于社团结构的网络空间复杂网络多尺度构建算法

网络空间要素及要素间关系构成的复杂网络进行可视化对感知网络结构和发现网络空间规律具有重要意义。针对网络空间复杂网络可视化时出现的大量节点和连边相互压盖造成的视觉混乱问题和基于层次聚类思想的社团划分算法构建的多尺度网络只能得到有限的尺度问题,提出一种基于社团结构的网络空间复杂网络多尺度构建方法。该方法基于改进的LFM社团发现算法,结合节点综合重要性进行社团核心节点的选取和依据社团间连边数量设定阈值建立重要节点不同层次连边,通过调整参数实现网络空间复杂网络多尺度构建。实验结果表明,该方法在构建多尺度网络过程中能够保留网络空间中的重要节点,相较于基于层次聚类思想的Louvain社团发现算法能够发现更多尺度的网络结构,且具有较好的连续性。

采用社会网络能力发现的众包服务节点选择算法

为了解决社会网络众包系统中由于潜在工作者未注册或注册用户的信息更新不及时而导致的服务节点选择不准确问题,提出了一种基于社会关系能力发现的网络众包服务节点选择算法。引入社会关系认知,以众包任务发布者或接受者个人为中心,利用社会网络的相关理论,提炼众包任务主题及相应的关键词,分析其与好友之间的交互信息中出现关键词的次数,结合其朋友圈中相应关键词的出现次数进行综合加权计算,量化朋友的能力大小,生成朋友能力矩阵,重构其社会关系。当众包任务生成或到达时,结合任务完成的质量因子、节点的诚信指数、匹配度等指标,有选择性地向符合能力要求的朋友进行任务转发。模拟微信交互的仿真实验表明:所提算法能较好地进行能力发现和选择合适的任务接受者,并且比随机分发平均节省了约64.5%的时间,可以实现快速精准的任务分发与数据收集。

基于SALSA的社交网络重要节点发现算法

社交网络中重要节点的发现研究具有较大的实际意义与价值。考虑社交网络中用户作为节点所包含一些特有的属性,通过将用户的社交行为划分强/弱关系的方式对社交网络拓扑结构的关系边进行补充,提出一种基于SALSA算法的加权算法WSALSA来发现社交网络中的重要节点。采用部分新浪微博真实数据进行实验及验证,对比PageRank、HITS和SALSA算法得到的节点影响力排序结果在SIR模型中的传播能力,结果表明WSALSA算法与SIR排序结果的斯皮尔曼相关系数值更高,对社交网络中节点重要性的评估更加准确。

融入节点重要性和标签影响力的标签传播社区发现算法

近年来,高质量社区的挖掘和发现已经成为社会网络研究一个热点.其中,基于标签传播的社区挖掘算法(Label Propagation Algorithm,简称LPA)由于具有近似线性时间复杂度且无须预先定义目标函数和社区数量等优点而得到广泛关注.但是,LPA算法的标签传播过程存在不确定性和随机性,影响了社区发现的准确性和稳定性.提出一种新的基于标签传播的社区发现算法LPA_SI(Label Propagation Algorithm based on Significance and Influence).首先,采用新的节点重要性度量方法对节点进行排序;其次,提出一种新的标签影响力计算方法更新每个节点的标签;最后,在真实数据集和人工数据集上的实验表明,LPA_SI在复杂度相近的情况下能够显著提高社区发现的质量,并具有较好的稳定性.

复杂网络牵制控制优化选点算法及节点组重要性排序

本文研究复杂网络动力学模型的无向网络牵制控制的优化选点及节点组重要性排序问题.根据牵制控制的同步准则,网络的牵制控制同步取决于网络的Laplacian删后矩阵的最小特征值.因此,通过合理选择受控节点集得到一个较大的Laplacian删后矩阵最小特征值,是牵制控制优化选点问题的核心所在.基于Laplacian删后矩阵最小特征值的图谱性质,本文提出了多个受控节点选取的递归迭代算法,该算法适用于任意类型的网络.通过BA无标度网络、NW小世界网络及一些实际网络中的仿真实验表明:该算法在控制节点数较少时,能有效找到最优受控节点集.最后讨论了在复杂网络牵制控制背景下节点组重要性排序问题,提出节点组的重要性排序与受控节点的数目有关.

微博社会网络重要用户节点筛选及舆情引导

首先通过研究网络爬虫以及新浪微博的开放平台,设计实现新浪微博专用爬虫,获取研究数据。其次,通过实验得到重要用户节点指标,提出贝叶斯-PageRank算法筛选重要用户节点,并实验验证重要用户节点的有效性。最后通过对重要用户节点的监测实现网络舆情发现并给出相关舆情引导策略。

微博社会网络用户节点重要性排序

微博用户节点重要性研究没有充分考虑到信息的高冗余性、传播速度快、时效性高等问题,为此构建基于贝叶斯模型的用户影响力计算方法。分析微博社会网络中用户的行为模式,使用贝叶斯网络模型进行用户节点属性的先验概率学习;通过人工标识重要用户节点,使用领域专家知识获取各属性的先验概率;对具有重要影响力的属性值进行学习,建立用户属性-影响力的贝叶斯网络模型,根据影响力排序得到微博社会网络用户节点重要性排序。实验结果表明,该方法可以显著识别重要用户节点。

基于LeaderRank和节点相似度的复杂网络重要节点排序算法

复杂网络中重要节点对网络结构和功能的影响引起了广泛关注。本文在现有Leader Rank算法的基础上,利用节点相似度来衡量节点间的相互作用,建立了SRank算法进行重要节点排序。利用SIR传播模型和斯皮尔曼等级相关系数在真实社会网络数据上对本文算法与经典的重要节点排序算法进行仿真后,发现该算法在无向和有向网络中均具有更高的准确性。

大规模数据下的社交网络结构洞节点发现算法研究

随着社会网络数据规模的递增,结构洞节点计算涉及的计算量呈几何级增长,如何构建有效的并行化算法并缩短算法运行的时间成为当前研究的难点。针对大规模数据量下结构洞节点发现算法的不足,利用并行化思想设计实现了基于MapReduce的结构洞节点发现算法。该算法通过DBLP,YouTube和Califonia公路网这3组规模不同的数据集在Hadoop集群上运行的实验结果表明,增加DataNode机器节点的数量能够缩短算法运行的时间,提高运行效率且具有良好的并行加速比和扩展性能。

基于节点重要性和模块度优化的社团划分算法

与无权网络相比,加权网络能够反映节点间关系的强弱,赋予复杂网络更加明确的物理意义,因此加权网络的社团划分具有重要的现实意义。为了提高加权网络社团划分的准确度,设计了一种基于节点重要性和模块度优化的加权网络社团划分算法IMWCD。首先,将每个节点初始化为一个社团,并借鉴度中心性和PageRank的评价思想,综合节点自身信息及其邻居节点信息来计算节点重要性;然后,按节点重要性的升序遍历节点,以模块度增益最大为原则将目标节点移入相应社团中,直至各节点不需要再移动;再以各个社团为节点重新构建网络,新网络中边的权重为两个新节点对应社团的权重之和;重复以上过程,直至网络的模块度不再变化。在LFR人工基准网络数据集和High-energy theory、Astrophysics和Condensed matter等真实加权网络上的实验结果表明,IMWCD算法的社团划分质量比同类型的算法有所提升,并且具有线性时间复杂度,能适用于大规模加权网络的社团划分。

基于节点重要度的城市轨道交通线网换乘协调优化

随着城市轨道交通规模扩大,车站数量增加,线间关联愈加密切。在网络化运营条件下,网络结构的复杂性、客流需求分布的不均衡性及列车运行组织方式的多样性,均对城市轨道交通运输计划提出更高的要求,在此提出基于节点重要度的城市轨道交通线网换乘优化方法。基于乘客出行选择行为对路径广义出行费用进行计算,建立基于时空出行网络的客流分配模型;依据影响城市轨道交通节点重要度的因素,提出网络内各区间及线路重要度的计算方法,基于线网内各节点、区间及线路的差异,构建基于节点重要度的城市轨道交通换乘协调优化模型;以成都地铁局部网络为例,验证模型的有效性。结果表明:所提出的协调优化模型将网络内站点、区间及线路3个层面的匹配度总共提升了34.58%,有效地提高了线网运输计划的运营效率。

受互联网思路启发的电力系统重要节点评估算法

对电力系统中重要节点进行有效区分,有助于在资源有限的条件下对重要节点施加额外保护或改变拓扑结构,从而提高系统鲁棒性、降低事故发生的概率。受网页排序算法启发,提出电气链接结构分析的随机方法(electrical stochastic approach for link structure analysis,E-SALSA)用于电力系统重要节点评估。该算法综合考虑了电力系统拓扑结构、潮流等因素对节点的影响,能够有效反映电力系统的真实情况,并且其特点更符合电力系统背景。在IEEE300节点电力系统中,使用失负荷规模和最大子群规模两个指标对E-SALSA算法与电气介数算法、基于共同引用的超链接引导的主题搜索(model based on co-citation hypertext induced topic search,MBCC-HITS)算法进行了对比分析。结果证明E-SALSA算法相比电气介数算法在两个指标上都具有优势,相比MBCC-HITS算法能够更综合考虑各方面因素对节点的影响,进而证明了E-SALSA算法的合理性、有效性。

区域城市公路货运节点重要度识别及网络构建研究

根据轴辐式网络理论,利用因子分析法对区域城市货运发展水平进行评价,得到单个城市的货运发展得分;引入引力模型和社会网络理论,明确枢纽城市及城市间的引力关系,然后基于隶属度模型确定枢纽城市辐射范围及隶属关系,最终确定区域公路货运网络的空间布局。以安徽省16个地级市为例进行分析,构建以合肥为主要轴心城市,芜湖、马鞍山、滁州、六安为次轴心城市,其他城市为辐点城市的区域公路货运网络,为区域货运网络构建与优化提供借鉴。

基于节点链接重要性的社区方法研究

关于社区结构较为常见的一种描述是关于强弱社区的阐述,一条边由2个节点构成,此2个节点对这条边有直接影响,是通过此2个节点的邻接点数目直接影响。除此之外,其间接关联性是通过此2个节点的公共邻居节点对网络其余部分的间接影响。文章从这2个方面考虑,得到一种新的社区发现算法。文章采用10个社区结构清晰度不同的人工生成网络数据集,通过与几种社区发现算法进行对比实验。实验证明,从几种不同的评价指标角度而言,文章研究算法在社区结构清晰度不同的人工生成网络数据集上都有较好的结果。

基于社区节点重要性的社会网络压缩方法

针对目前图压缩方法中存在的时间复杂度较高、依赖先验知识设定参数、需要调节的参数过多、压缩有损、忽视网络社区结构等问题,提出基于社区节点重要性的社会网络压缩方法。该方法由基于贪婪策略的社区发现算法(GS)和社会网络压缩算法(SNC)两部分组成。GS算法采用拓扑势理论,不但可以实现社区发现,而且可挖掘出社区中的重要节点。SNC算法以网络社区为压缩对象,在保持社区间的关联关系的前提下实现了无损压缩,并可在必要时保留社区中的重要节点或基本结构。通过实验,对方法的可行性和有效性进行了验证。

基于用户紧密度的在线社会网络社区发现算法

针对在线社会网络潜在社区难以检测的问题,根据在线社会网络的独有特性,提出一种基于用户紧密度的在线社会网络社区发现算法。创建初步用户图,依据节点属性相似性算法计算用户个体紧密度,基于共有邻居相似性算法计算用户社区紧密度,从而构造出完整用户图,利用层次聚类算法对完整用户图进行处理,发现潜在社区。实验结果表明,与NAS、CNS算法相比,该算法的社区凝聚度与正确率更高,分别达到0.67和97.1%。