检测网络社团结构的基于最短路径的$k$-均值算法

我们考虑复杂网络社团结构的检测问题,即检测出那些具有高于平均密度的边所连接的节点的集合.本文我们利用模拟退火策略来极大化可表示为稳定效益函数的模量(modularity),并结合基于最短路径的$k$-均值迭代过程来对网络进行分区.该算法不仅能检测出社团,而且能够识别出在最短路径度量下,该社团中位于中心位置的节点.社团的最优数目可以在无需任何关于网络结构的先验信息下自动确定.对人工生成网络和真实世界中的网络的成功应用表明了算法的有效性.     

考虑对象属性信息的复杂网络社团结构发现算法

针对社团结构发现算法仅考虑对象间相互关系的密集程度,忽视对象间属性特征差异的不足,提出考虑属性信息的复杂网络社团结构发现算法.算法引入属性特征相似度、基于属性特征相似度的有权网络、内聚度3个核心概念,迭代选取使内聚度指标上升最快的合并操作,自底向上实现社团聚集.由于考虑了属性信息,算法输出的社团结构具有更高准确度,更具应用价值.     

基于动态系统的网络社团线性探测算法

社团探测技术对于理解和分析现实世界网络具有非常重要的意义.本文提出了一种新的动态社团探测算法,利用迭代技术高效而准确地揭示网络中的社团结构.首先引入一种新型的基于离散时间的动态系统,描述社团归属的从随机状态到最优划分的演化轨迹,进一步利用严格的数学分析找出了社团归属收敛到最优的条件.另外,本文还创新性地提出了划分指标函数的一般化形式,通过选择不同的参数,可以引申到几乎所有著名的指标函数.本文算法非常高效,计算复杂度分析显示算法需要的时间与稀疏网络节点的数量呈线性关系.除此之外,为了确定社团的最优数目,本文利用Markov状态转移矩阵及其特征系统给出了具体而严格的求解证明.最后,本文将算法应用到人工网络和实际网络中,结果显示算法不仅具有极高的准确性,还能够揭示很多有用的隐藏信息,如层次结构和社团交互模式等.     

多社团加权复杂网络建模及其级联抗毁性研究

为了研究社团结构和权重因素对网络级联抗毁性的影响,引入节点和边的消亡机制,建立了一类具有社团结构的加权网络模型.采用本方法生成网络的度、强度和边权分布都呈现无标度特性,比现有BBV (Barrat-Barthelemy-Vespignani)模型具有更好的社团结构特性,且幂律指数、模块度参数可调.在此基础上研究了网络的级联抗毁性,采用节点及其邻居节点强度的函数定义网络负荷,故障节点负荷采用"局部定义,局部分配"的策略.仿真分析了边权演化参数、模块度函数、攻击策略和演化时间对网络级联抗毁性的影响.结论表明,网络的抗毁性与边权演化参数、网络演化时间成反比,与模块度的关系不是单调的而是存在一个阈值.优先攻击度最大节点的策略对网络抗毁性破坏最大,且在多节点遭受攻击时,网络的故障规模会发生突变.文章的研究结论对故障的预防与控制以及网络的建设具有一定的参考价值.     

节点动态增长对复杂网络传输效率的影响研究

在真实的复杂网络中,网络节点会因为网络拓扑结构的变化而增减,进而导致网络节点间传输效率降低.针对这一问题,通过分析复杂网络节点的动态变化,提出网络节点增加的动态传输模型,并利用真实复杂网络的数据模拟仿真,研究网络节点变化对网络传输效率的影响.结果表明:网络的初始大小会随网络节点的动态增加而变化,其传输效率受节点动态增加的影响在最初阶段表现明显,随着节点的继续增加,网络传输效率会趋于平稳,表现出稳定的网络特性.在这个过程中,复杂网络每次新加入节点的个数和节点边维持了网络信息传输的信息量,强化了网络传的输性能,使得网络具有较好的总体控制能力和有效的节点连接方式.     

基于加权复杂网络的文本关键词提取

通过分析基于复杂网络的网络提取的文本关键词新算法.首先根据文本特征词之间的关系构建文本的加权复杂网络模型,其次通过节点的加权聚类系数和节点的介数计算节点的综合特征值,最后根据综合特征值提取出文本关键词.实验结果表明,该算法提取的关键词能够较好地体现文本主题,提取关键词的准确率比已有算法有明显提高.     

复杂网络在双曲空间的节点动态择优路径研究

本文研究复杂网络双曲嵌套模型.利用改进克林伯格和克莱尔科夫网络拓扑模型的方法,得到了复杂网络在双曲空间的动态择优路径,推广和发展了复杂网络节点间最优路径的算法.     

基于复杂网络的沪深300股票重要节点的评估和分析

利用复杂网络方法将股票之间的复杂关系抽象为网络,能够更好地掌握股票市场的整体和局部特性以及股票之间内在的联动关系,以沪深300数据为研究样本,通过相关系数构建网络,利用最佳阈值法对网络进行去噪,保留主要股票之间的相互影响.借鉴PageRank算法对社团网络进行重要节点的挖掘,从宏观和微观视角分析各行业股票在市场中的地位.研究发现整个沪深300市场中,采矿业、制造业和金融业是市场"大户",其股票与市场中的其他股票之间存在紧密联系;网络中的同类型股票存在聚集现象,且股票之间影响关系显著.     

Bellman最优原理在复杂加权网络中的应用研究

针对现有算法及软件计算复杂加权网络介数的局限性,应用Bellman最优原理于复杂加权网络介数计算中,并针对复杂网络动态演化,节点众多,重点,节点间无边连接等特点作了相应修改.依算法实例计算出了复杂加权网络的最短路径长、最短路径和介数,最后经验证算法具有较快的运行速度和较准确的结果.     

基于网络拓扑结构的重要节点发现算法

复杂网络中的重要节点发现在现实生活中有着广泛的应用价值。传统重要节点发现方法可分为局部发现和全局发现两类算法,全局发现算法中最具代表性的是特征向量中心性算法(Eigenvector Centrality, EC),EC算法将所有节点归为一个社区并利用邻居节点重要性反馈计算节点的影响力大小,具有较高的计算效率和识别精度。但是,EC算法忽略了网络的拓扑结构,未考虑到真实网络中节点所在社区的结构特征。为此,本文提出一种基于网络拓扑结构的可达中心性算法(Accessibility Centrality, AC),首先利用邻接矩阵作为反馈路径,在反馈过程中计算不同路径下的节点整体影响力。同时,利用影响力传递过程中的噪音干扰特性,修正每一路径长度下节点整体影响力大小,最后利用修正结果得到AC值。为评估AC算法,本文利用两种传染病模型模拟节点影响力在四组真实网络中的传播过程,并引入其他四种算法进行对比验证。实验结果表明,与其他算法相比,AC算法可以更准确、有效地识别出有具有影响力的重要节点。     

Traffic Flows and Product Form Solutions in Stochastic Transfer Networks

This paper focuses on product form and related tractable stationary distributions in a general class of stochastic networks with finite numbers of nodes such that their network states are changed through signal transfers as well as internal transitions. Signals may be customers in traditional queueing applications, but we do not make any restriction on their effects at departing as well as arriving nodes. They may also instantaneously move around among different nodes. Furthermore, signal routing may depend on the whole network state. For analytical simplicity, we assume that the state space is countable. For such a network, we propose an abstract model, called a stochastic transfer network, and consider the stationary distribution of the network state. We introduce conditional traffic rates for arrivals and departures. Using them, we consider when the network has product form or some other tractable stationary distributions.     

Discovery Through Gossip

We study randomized gossip‐based processes in dynamic networks that are motivated by information discovery in large‐scale distributed networks such as peer‐to‐peer and social networks. A well‐studied problem in peer‐to‐peer networks is resource discovery, where the goal for nodes (hosts with IP addresses) is to discover the IP addresses of all other hosts. Also, some of the recent work on self‐stabilization algorithms for P2P/overlay networks proceed via discovery of the complete network. In social networks, nodes (people) discover new nodes through exchanging contacts with their neighbors (friends). In both cases the discovery of new nodes changes the underlying network — new edges are added to the network — and the process continues in the changed network. Rigorously analyzing such dynamic (stochastic) processes in a continuously changing topology remains a challenging problem with obvious applications. This paper studies and analyzes two natural gossip‐based discovery processes. In the push discovery or triangulation process, each node repeatedly chooses two random neighbors and connects them (i.e., “pushes” their mutual information to each other). In the pull discovery process or the two‐hop walk, each node repeatedly requests or “pulls” a random contact from a random neighbor and connects itself to this two‐hop neighbor. Both processes are lightweight in the sense that the amortized work done per node is constant per round, local, and naturally robust due to the inherent randomized nature of gossip. Our main result is an almost‐tight analysis of the time taken for these two randomized processes to converge. We show that in any undirected n‐node graph both processes take rounds to connect every node to all other nodes with high probability, whereas is a lower bound. We also study the two‐hop walk in directed graphs, and show that it takes time with high probability, and that the worst‐case bound is tight for arbitrary directed graphs, whereas Ω(n²) is a lower bound for strongly connected directed graphs. A key technical challenge that we overcome in our work is the analysis of a randomized process that itself results in a constantly changing network leading to complicated dependencies in every round. We discuss implications of our results and their analysis to discovery problems in P2P networks as well as to evolution in social networks. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 48, 565–587, 2016     

Stable and emergent network topologies: A structural approach

Economic, social and military networks have at least one thing in common: they change over time. For various reasons, nodes form and terminate links, thereby rearranging the network. In this paper, we present a structural network mechanism that formalizes a possible incentive that guides nodes in constructing their local network structure. The mechanism assumes that nodes deliberately form and terminate links as they attempt to gain network advantage and/or an identifiable position in the network. Reiteration of this mechanism, which only uses local network characteristics, results in emergent, stable network topologies. Examples are uni-polar networks, bi-polar networks and cycle-networks. This process illustrates that local, binary decisions shape global network structures. These results may be used to derive some rules of thumb for designing networks.     

广播网络的最佳源点集

广播是研究通信网络的某个成员的消息如何尽快地传递给所有其它成员的消息传递问题,有两类常见的通信模式,一类是shouting模式,即在一个单位时间内,一个顶点能够和它的户斤有邻点通信;另一类是whispering模式,即在一个单位时间以内,一个顶点最多只能和它的一个邻点通信,通信网络通常用图来描述,最初贮存消息的网络成员称为源点。     

网络部分结点最佳连通关系的逐步生成法

提出了一种就现有公路网中 ,在对其部分结间的连通关系进行技术等级升级时 ,生成以连通这些目标结点为目的的最小树生成方法——逐步生成法 .     

����ά�DZ���Jackson����ļ�����Ϊ

??For the infinite Jackson network, assume that the net input rates are greater than the service rates for some nodes. Via solving the new throughput equation, the stochastic comparable processes are obtained by coupling method, and furthermore the limits for the queueing length in all nodes are also obtained. Despite the whole network is non-ergodic, it is possible to get the maximal ergodic subnetwork.     

On pinning control of some typical discrete-time dynamical networks

Recently, the pinning control of complex dynamical networks to their homogeneous states has been studied by many researchers, most of the dynamical networks are continuous-time ones, i.e., their dynamical behavior can be described by ODEs. An interesting result is that, for a continuous-time network, its desired (homogeneous) state can be achieved by pinning some nodes with relatively large degrees (also called the specifically pinning scheme [Wang XF, Chen GR. Pinning control of scale-free dynamical networks. Physica A 2002;310:521–31]). Is this specifically pinning scheme also effective for the discrete-time dynamical networks? In this paper, we demonstrate that the pinning control for a discrete-time dynamical network is difficult, and sometimes it is impossible to achieve the desired state just by controlling the nodes with larger degrees. In order to control the discrete-time dynamical networks successfully, we may need to control all the nodes. Finally, we also consider how to extend the interval for the feedback gain d for successful control.     

Modeling cooperation on a class of distribution problems

In this paper we study models of cooperation between the nodes of a network that represents a distribution problem. The distribution problem we propose arises when, over a graph, a group of nodes offers certain commodity, some other nodes require it and a third group of nodes neither need this material nor offer it but they are strategically relevant to the distribution plan. The delivery of one unit of material to a demand node generates a fixed profit, and the shipping of the material through the arcs has an associated cost. We show that in such a framework cooperation is beneficial for the different parties. We prove that the cooperative situation arising from this distribution problem is totally balanced by finding a set of stable allocations (in the core of an associated cooperative game). In order to overcome certain fairness problems of these solutions, we introduce two new solution concepts and study their properties.     

改进的CATSMLP预警藻类污染

人工神经网络由于其很多的特点与优势现已被广泛关注和运用.但是人工神经网络也存在学习过程易陷入局部极小、易出现震荡和网络存在冗余连接或节点等缺陷.针对这些不足,一种新的级联M LP神经网络CATSM LP比ATSM LP有更好的鲁棒性和高度的解释性,并且是一个万能逼近器.采用粒子群优化算法对其进行优化使其鲁棒性增强,具有更快速的收敛能力和更好的寻优能力,从而能更有效的建模.藻类的生长是湖泊等水体污染程度的一个直接表现形式.在某些情况下,甚至精密仪器都不能测出某些藻类污染物,因此需要好的方法越来越受到专家学者们的重视.将其用于藻类污染预警,仿真试验表明其用于环境污染防治有很好的效果,值得推广应用.     

Evaluating the robustness of temporal networks considering spatiality of connections

Network robustness has been a hot research area of studies on complex networks. Finding out the explanations behind the phenomena that networked systems can still function efficiently after some structural damages or the malfunction of certain nodes is meaningful to both the design of solid systems and the defend against failures. It is still indistinct what kind of resilience networked systems which change their topological structures incessantly over time might have. Nevertheless, earlier studies have frequently overlooked to consider the temporal characteristics which in many real scenarios are of great concern, or have considered only the temporality without spatiality which is not reasonable in the real world case. In this paper, we first take the spatiality of connections and communications between nodes, except for the temporal ordering of connection events which has solely been noticed by previous studies, into consideration for measuring and assessing the robustness of the temporal network. We propose a novel temporal efficiency metric, and correspondingly, develop a new temporal robustness evaluation method for temporal network models. The proposed metric and method show their validity through numerical simulations of three temporal network models and we give our evaluations and discussions.