小世界网络抗毁性及介-度相关性研究

日常生活中,复杂网络主要面临随机攻击和选择性攻击,网络模型的结构特性使复杂网络在不同攻击方式下的抗毁性有很大的差异.综合考虑复杂网络的抗毁性参数和网络模型的结构特性差异,文章以节点的最大度值、平均度值、最大介数和平均介数为度量参数,通过5种不同攻击方式对WS小世界网络的抗毁性进行了测试,得到了介度关系曲线,随着节点的移除,动态分析了WS小世界网络的抗毁性和攻击下小世界网络的介 度相关性.实验结果表明,WS小世界网络在RD攻击下表现出一定的脆弱性,在其他攻击方式下有很强的鲁棒性,而其介度关系在某些区域呈线性关系,但大部分区域呈现无规律性,其动态相关性需要进一步研究.小世界网络较强的抗毁性对组建网络有重要的影响,鉴于小世界网络的结构特性,组建网络时应尽量不要把网络的功能集中在少数Hub节点上.针对WS小世界网络较强的鲁棒性,结合小世界网络的结构特性,将做进一步研究,以便提出更高效的攻击策略.     

基于社区的动态网络节点介数中心度更新算法

随着互联网技术的迅猛发展,社会网络呈现出爆炸增长的趋势,传统的静态网络分析方法越来越难以达到令人满意的效果,于是对网络进行动态分析就成为社会网数据管理领域的一个研究热点。节点介数中心度衡量的是一个节点对图中其他点对最短路径的控制能力,有利于挖掘社会网络中的重要节点。在图结构频繁变化的场合,若每次变化后都重新计算整个图中所有节点的介数中心度,则效率将会很低。针对动态网络中节点介数中心度计算困难的问题,本文提出一种基于社区的节点介数中心度更新算法。通过维护社区与社区、社区与节点的最短距离集合,快速过滤掉那些在网络动态更新中不受影响的点对,从而大大提高节点介数中心度的更新效率。真实数据集和合成数据集上的实验结果表明了论文所提算法的有效性。     

基于重叠社区和结构洞度的社会网络结构洞识别算法

结构洞是社会网络中的关键位置,对信息扩散起中介作用。为高效、准确地辨识具有社团结构的社会网络中占据结构洞的节点,提出了一种基于重叠社区和结构洞度的结构洞识别算法,旨在找到一组最具信息优势和控制优势的节点。基本思想是首先定位社区之间的重叠节点,然后利用节点的邻接差异和连接的社区差异衡量其非冗余性,计算出重叠节点的结构洞度,通过对结构洞度值升序排列发现占据结构洞的节点集。应用于实际数据集的实验结果表明,与网络约束系数算法、中介中心度算法、MaxD算法相比,该算法的识别准确度最高,时间复杂度最低。     

基于中介中心度的微博影响力个体发现

微博中重要影响力个体的发现有着极为重要的作用。中介中心度方法是发现网络中重要节点的有效方法, 然而传统的中介中心度方法只适用于小规模的网络, 对于海量的微博网络信息却无能为力。提出一种基于随机游走的中介中心度算法, 该算法不仅能有效地应对海量的微博网络数据, 而且其发现结果也明显优于相关的研究。     

基于节点亲密度的重要性评估算法

识别复杂网络中的重要节点一直是社会网络分析和挖掘领域的热点问题,有助于理解有影响力的传播者在信息扩散和传染病传播中的作用。现有的节点重要性算法充分考虑了邻居信息,但忽略了邻居节点与节点之间的结构信息。针对此问题,考虑到不同结构下邻居节点对节点的影响力不同,提出了一种综合考虑节点的邻居数量和节点与邻居间亲密程度的节点重要性评估算法,其同时体现了节点的度属性和"亲密"属性。该算法利用相似性指标来测量节点间的亲密程度,以肯德尔相关系数为节点排序的准确度评价指标。在多个经典的实际网络上利用SIR(易感-感染-免疫)模型对传播过程进行仿真,结果表明,与度指标、接近中心性指标、介数中心性指标与K-shell指标相比,KI指标可以更精确地对节点传播影响力进行排序。     

Centrality prediction in dynamic human contact networks

Real technological, social and biological networks evolve over time. Predicting their future topology has applications to epidemiology, targeted marketing, network reliability and routing in ad hoc and peer-to-peer networks. The key problem for such applications is usually to identify the nodes that will be in more important positions in the future. Previous researchers had used ad hoc prediction functions. In this paper, we evaluate ways of predicting a node’s future importance under three important metrics, namely degree, closeness centrality, and betweenness centrality, using empirical data on human contact networks collected using mobile devices. We find that node importance is highly predictable due to both periodic and legacy effects of human social behaviour, and we design reasonable prediction functions. However human behaviour is not the same in all circumstances: the centrality of students at Cambridge is best correlated both daily and hourly, no doubt due to hourly lecture schedules, while academics at conferences exhibit rather flat closeness centrality, no doubt because conference attendees are generally trying to speak to new people at each break. This highlights the utility of having a number of different metrics for centrality in dynamic networks, so as to identify typical patterns and predict behaviour. We show that the best-performing prediction functions are 25% more accurate on average than simply using the previous centrality value. These prediction functions can be efficiently computed in linear time, and are thus practical for processing dynamic networks in real-time.     

复杂网络中的一种介度熵抗毁性度量方法

在复杂网络中，核心节点的损坏可能会影响到整个网络的稳定性。基于节点重要性研究了网络抗毁性度量和抗毁性能。综合考虑节点度值和介数对节点重要性的影响，提出了局部介-度中心性指标。兼顾节点的聚集系数，提出节点抗毁性度量方法。为了估量网络的抗毁性能，提出了介-度熵度量及其算法。仿真攻击实验结果表明，基于介-度中心性的攻击策略移除约20%的节点后，可将网络近似地分割为孤立节点集合，它优于传统的攻击策略，表明介-度中心性指标可以更准确地刻画节点重要性。对不同模拟网络的抗毁性评估计算结果则表明，介-度熵度量对网络抗毁性能的排序符合实际情况，在衡量网络抗毁性方面是完全合理的。     

一种基于最短路径介数的重要节点发现算法

网络中重要节点的发现是研究网络特性的重要方面之一,在复杂网络、系统科学、社会网分析和互联网搜索等领域中具有广泛的应用价值。为提高全网范围内重要节点发现的效率和有效性,提出了一种基于最短路径介数及节点中心接近度的重要节点发现算法,通过最短路径介数的方法确定全网内的重要节点,利用中心接近度分析重要节点的重要性。测试结果表明,与同类的系统比较起来,该方法具有比较好的性能。     

用户关系特征对微博转发行为影响分析研究

转发是微博提供的一个信息传播的机制,用户能够将关注者发布的有趣微博转发到自身平台,然后分享给追随者,是微博网络中信息传播最重要的功能。对于微博网络存在的不同类型连接关系,首先提取出相关特征,如同质性、微网络结构、地理距离以及用户性别等,用于识别连接关系的不同类型,然后采用Log-linear模型来拟合各个特征间系数,基于这些系数对微博用户转发行为形成的内在原因进行了分析。     

Predicting temporal centrality in Opportunistic Mobile Social Networks based on social behavior of people

Predicting the centrality of nodes is a significant problem for different applications in Opportunistic Mobile Social Networks (OMSNs). However, when calculating such metrics, current studies focused on analyzing static networks that do not change over time or using aggregated contact information over a period of time. Furthermore, the centrality measured in the past is not verified whether it is useful as a predictor for the future. In this paper, in order to capture the dynamic behavior of people, we focus on predicting nodes’ future centrality (importance) from the temporal perspective using real mobility traces in OMSNs. Three important centrality metrics, namely betweenness, closeness, and degree centrality, are considered. Through real trace-driven simulations, we find that nodes’ future centrality is highly predictable due to natural social behavior of people. Then, based on the observations in the simulation, we design several reasonable prediction methods to predict nodes’ future temporal centrality. Finally, extensive real trace-driven simulations are conducted to evaluate the performance of our proposed methods. The results show that the Recent Weighted Average Method performs best in the MIT Reality trace, and the recent Uniform Average Method performs best in the Infocom 06 trace. Furthermore, we also evaluate the impact of parameters m and w on the performance of the proposed methods and find proper values of different parameters for each proposed method at the same time.     

复杂社会网络的介数性质近似计算方法研究

随着计算机和互联网的迅猛发展,面向互联网的社会网络挖掘和分析成为一个新的课题。从互联网挖掘的社会网络往往规模巨大,这对网络分析算法的性能提出了更高的要求 。介数值作为图的重要结构性质,广泛应用于基于图的聚类、分类算法,如何降低其计算的复杂性是急需解决的问题。目前,常用的方法是利用对最短路径长度的近似来降低低网络分析算法的复杂性,但已有的近似方法没有考虑现实大规模网络的复杂网络特性,对最短路径长度的近似方 近似计算方法,其基本思想是结合复杂网络的结构特性,利用通过网络中枢节点的路径来近似最短路径,以近似的最短路径求得介数的近似值。这为图的结构性质的近似估算算提供了一种新颖的思路。通过与传统的介数计算方法和近的分析得到了若干有益的结论,为进一步的研究工作奠定了基础。     

基于影响度介数中心性的多智能体牵制控制算法

针对多智能体系统在牵制控制过程中最终收敛时系统稳定性较差的问题,设计一种影响度矩阵,重新构建介数中心性算法来完成牵制控制节点选择工作.首先,根据子网的度分布计算影响度矩阵;其次,由影响度矩阵计算子网的介数中心性分布矩阵;最后,根据介数中心性选择牵制控制节点,既保留个体本身的重要性,也引入邻居个体重要性对其影响程度.经过对比实验验证了影响度介数中心性算法可有效增强多智能体系统的鲁棒性并提高系统的收敛速度.     

Organisational adaptation in an activist network: Social networks,leadership, and change in al-Muhajiroun

Social networks are said to facilitate learning and adaptation by providing the connections through which network nodes (or agents) share information and experience. Yet, our understanding of how this process unfolds in real-world networks remains underdeveloped. This paper explores this gap through a case study of al-Muhajiroun, an activist network that continues to call for the establishment of an Islamic state in Britain despite being formally outlawed by British authorities. Drawing on organisation theory and social network analysis, we formulate three hypotheses regarding the learning capacity and social network properties of al-Muhajiroun (AM) and its successor groups. We then test these hypotheses using mixed methods. Our methods combine quantitative analysis of three agent-based networks in AM measured for structural properties that facilitate learning, including connectedness, betweenness centrality and eigenvector centrality, with qualitative analysis of interviews with AM activists focusing organisational adaptation and learning. The results of these analyses confirm that al-Muhajiroun activists respond to government pressure by changing their operations, including creating new platforms under different names and adjusting leadership roles among movement veterans to accommodate their spiritual leader's unwelcome exodus to Lebanon. Simple as they are effective, these adaptations have allowed al-Muhajiroun and its successor groups to continue their activism in an increasingly hostile environment.     

基于节点重要度的复杂网络可靠性研究

为研究复杂网络的节点重要度及其可靠性,在随机网络、小世界网络和无标度网络模型下,理论分析度值中心性、半局部中心性、介数中心性和PageRank算法在节点重要度评估上的准确性,通过仿真模拟方法,对网络理论模型和实际复杂网络分别进行研究,采用逐步移除节点和重复计算的方式,考察网络最大连通子图和节点移除比例的关系,同时对数值仿真结果进行合理分析。研究结果说明基于网络全局信息的介数中心性和PageRank算法对节点重要度评估的效果更好,同时说明网络的可靠性与网络拓扑结构有关,实际复杂网络一般同时具备多种拓扑特性。     

基于代数连通性的复杂网络割边模型研究

传统的GN算法每次迭代删除一条边,时间复杂度高,其变种时间复杂度有所下降,但分割精度也有待于提高;在复杂网络图中,图的连通性是由拉普拉斯矩阵的第二小特征值决定的,通过最小化网络连通性,提出了贪婪谱优化割边模型,该模型在GN算法基础上,一次删除多条边,为避免出现边过度分割,每条边设置了权重;为了进一步降低时间复杂度,选择网络代数连通性下降最快的边进行删除,提出了基于边中心性测度的割边模型,与传统的利用最短距离和随机游走不同,模型采取谱分析方法对每条边定义边中心性测度,速度更快,分割精度能到达要求,适合处理中规模社区结构。     

基于多层次灰色关联分析的复杂网络节点排序模型

复杂网络节点重要性是研究复杂网络特性的重要方面之一,被广泛应用于数据挖掘、Web 搜索、社会网络分析等众多研究领域。在选取评估节点重要性指标时,考虑到普通聚类系数仅能衡量网络节点聚类的疏密度,不能衡量聚类的规模,提出了修正的聚类系数;同时,选取了Erdos数和介数两个指标来综合衡量网络节点重要性,建立多层次 灰色关联分析模型,确定出各个节点与理想节点的关联度,实现对复杂网络节点的排序。模型不仅考虑到度、路径距离对节点排序的影响,而且也考虑到每个节点聚类程度对节点排序的影响。通过与实际网络和其他方法的排序结果对比,模型能够准确找到复杂网络的核心节点,并且排序结果真实反映了节点依次的重要程度。     

改进的SCIR模型中社交网络信息传播研究

社交网络中用户转发是信息传播的重要渠道,研究用户转发模式和信息传播规律,将有利于在网络话题传播过程中进行监控和抑制。现有的建模研究中,存在模型通常缺少时效性,用户行为难以准确刻画的问题。因此,着重分析了社交网络用户行为模式,基于用户连接强度和邻居节点的影响改进了转发概率计算,其次在经典的传染病动力学SCIR模型中,引入在线和离线状态的节点,通过用户在线比率控制网络活跃度。仿真结果表明,该模型相较传统SCIR模型在信息传播过程中具有较好的稳定性和更高的覆盖率,节点属性变化走势更加接近真实网络,可以较好地模拟社交网络中的热点话题的传播规律。     

基于信息传播影响因素的边重要性度量方法

在信息传播中,边的重要性度量是一个非常重要的研究问题。边是信息传播的载体,不同位置的边具有不同的信息负载和传播能力。移除一些对传播有重要影响的边对遏制谣言的传播和公共信息的传播最大化等有重要意义。信息的传播易受传播者、受传者、传播渠道和传播环境等影响。基于这些观察,通过综合考虑影响信息传播的多种因素,提出一种基于信息传播影响因素的边重要性度量方法ISM。在9个真实网络数据集上,ISM与4个经典的边重要性方法的Jaccard系数、桥度指数、介数中心性和可达性指数进行了比较。实验结果表明,该方法在网络连通性和扩散动态过程中,对于重要边的识别均优于其他常用方法。     

Organizational structure of Mazda’s Keiretsu: a graph theoretic analysis

According to Freeman, centrality indices, which include degree, closeness, and betweenness, are an effective way to measure organizational structure. However, Ito discussed the implications of centrality, and found that differences exist even when the centrality is the same. Using data on transactions and cross shareholdings that were drawn from Mazda’s Yokokai Keiretsu, a new method — the SNW model — is proposed to calculate structural importance. Therefore, this article provides a new perspective for discovering the structural importance of network organizations. Furthermore, implications based on statistical comparisons between the SNW model and corporate performance such as sales and profits are proffered.     

基于PageRank的微博用户影响力算法研究

随着Web技术的发展,微博已经成为最受欢迎的社交平台之一了。在中国,微博用户规模已经达到了2.42亿。微博用户影响力计算对社会信息在微博里面有效传播,正确传播,健康传播有着非常重要的意义。本文以新浪微博数据为实验的对象,通过改进传统的PageRank模型,提出了的新型用户影响力排名算法---MBUI-Rank(Micro-Blog User Influence Rank)算法。在考虑传统PageRank方法的用户链接关系的同时,MBUI-Rank算法还考虑到微博用户自身行为活动,构建用户对微博的影响的动态挖掘模型。实验结果表明,MBUI-Rank算法与传统的PageRank算法相比,可以更加真实有效地反映微博用户的实际影响力。