Measuring centrality by a generalization of degree

Network analysis has emerged as a key technique in communication studies, economics, geography, history and sociology, among others. A fundamental issue is how to identify key nodes, for which purpose a number of centrality measures have been developed. This paper proposes a new parametric family of centrality measures called generalized degree. It is based on the idea that a relationship to a more interconnected node contributes to centrality in a greater extent than a connection to a less central one. Generalized degree improves on degree by redistributing its sum over the network with the consideration of the global structure. Application of the measure is supported by a set of basic properties. A sufficient condition is given for generalized degree to be rank monotonic, excluding counter-intuitive changes in the centrality ranking after certain modifications of the network. The measure has a graph interpretation and can be calculated iteratively. Generalized degree is recommended to apply besides degree since it preserves most favourable attributes of degree, but better reflects the role of the nodes in the network and has an increased ability to distinguish among their importance.     

Distributed computation of virtual coordinates for greedy routing in sensor networks

Sensor networks are emerging as a paradigm for future computing, but pose a number of challenges in the fields of networking and distributed computation. One challenge is to devise a greedy routing protocol—one that routes messages through the network using only information available at a node or its neighbors. Modeling the connectivity graph of a sensor network as a 3-connected planar graph, we describe how to compute on the network in a distributed and local manner a special geometric embedding of the graph. This embedding supports a geometric routing protocol called “greedy routing” based on the “virtual” coordinates of the nodes derived from the embedding.     

Network representation of dynamical systems: Connectivity patterns,information and predictability

The present work elaborates on predictability and information aspects of dynamical systems, in connection with the connectivity features of their network representation. The basic idea underlying this work is to map the set of coarse-grained states of a dynamical system onto a set of network nodes and transitions between them onto a set of network links. Based on the vertex centrality of these nodes, we define (a) a local indicator of predictability, (b) a measure of the information that is available about the state of the system after one transition occurring within an arbitrary long time window and (c) an upper bound for the time horizon of predictability. We address the cases of the tent and the cusp maps, as representative examples of Markov and non-Markov processes. An analytical exact result for the horizon of predictability is obtained for the tent map, as well as for its higher iterates, and its connection with the corresponding network diameters is discussed. Similarly, analytical expressions are derived for the bounds of the predictability horizon in the case of the cusp map.     

Analysis of complex network performance and heuristic node removal strategies

Removing important nodes from complex networks is a great challenge in fighting against criminal organizations and preventing disease outbreaks. Six network performance metrics, including four new metrics, are applied to quantify networks’ diffusion speed, diffusion scale, homogeneity, and diameter. In order to efficiently identify nodes whose removal maximally destroys a network, i.e., minimizes network performance, ten structured heuristic node removal strategies are designed using different node centrality metrics including degree, betweenness, reciprocal closeness, complement-derived closeness, and eigenvector centrality. These strategies are applied to remove nodes from the September 11, 2001 hijackers’ network, and their performance are compared to that of a random strategy, which removes randomly selected nodes, and the locally optimal solution (LOS), which removes nodes to minimize network performance at each step. The computational complexity of the 11 strategies and LOS is also analyzed. Results show that the node removal strategies using degree and betweenness centralities are more efficient than other strategies.     

On a matrix-based measure of the degree of coreness of a node in a network

The paper focuses on the right and left eigenvectors of a network matrix that belong to the largest eigenvalue. It is shown that each of vector entries measures the walk centrality of the corresponding node’s position in the network’s link structure and of the positions of the node’s adjacent nodes; as a result, it indicates to which degree the node can be associated with the structure’s core, i.e., the structural coreness of the node. The relationship between the vectors’ coordinates and the position of the nodes, as well as the actual computation of the coordinates, is based on an iterative computational scheme known as the power method. The paper studies the method’s convergence for networks of different structure. Some possible applications are discussed. The paper also includes a numerical example dealing with a real network of 197 nodes and 780 links.     

Optimized network structure for full-synchronization

A network of Kuramoto oscillators with different natural frequencies is optimized for enhanced synchronizability. All node inputs are normalized by the node connectivity and some important properties of the network structure are determined in this case: (i) optimized networks present a strong anti-correlation between natural frequencies of adjacent nodes; (ii) this anti-correlation should be as high as possible since the average path length between nodes is maintained as small as in random networks; and (iii) high anti-correlation is obtained without any relation between nodes natural frequencies and the degree of connectivity. We also propose a network construction model with which it is shown that high anti-correlation and small average paths may be achieved by randomly rewiring a fraction of the links of a totally anti-correlated network, and that these networks present optimal synchronization properties.     

一种基于tit-for-tat策略的伪度优先算法

复杂网络中的两个节点,随着时间的推移,由于利益冲突,可能会采取一些行动,合作或者背叛,对于背叛过多的节点,需要断开重连,这也恰好反映了现实情况.根据重复博弈中的tit-for-tat策略,提出了一种伪度优先算法,研究了在不改变节点个数情况下,复杂网络的统计特性.仿真结果表明,该算法并不改变网络的无标度特征,但是改变了最大度的节点分布,并且大大提高了网络的聚集系数.另外,还研究了对网络社团结构的影响,结果表明可以优化网络的社团结构.     

Modeling centrality measures in social network analysis using bi-criteria network flow optimization problems

Centrality measures play an important role in the field of network analysis. In the particular case of social networks, the flow represents the way in which information passes through the network nodes. Freeman et al. (1991) were the first authors to relate centrality measures to network flow optimization problems in terms of betweenness, closeness, and the influence of one node over another one. Such measures are single dimensional and, in general, they amalgamate several heterogeneous dimensions into a single one, which is not suitable for dealing with most real-world problems. In this paper we extend the betweenness centrality measure (or concept) to take into account explicitly several dimensions (criteria). A new closeness centrality measure is defined to deal not only with the maximum flow between every ordered pair of nodes, but also with the cost associated with communications. We shall show how the classical measures can be enhanced when the problem is modeled as a bi-criteria network flow optimization problem.     

Percolation in the secrecy graph

The secrecy graph is a random geometric graph which is intended to model the connectivity of wireless networks under secrecy constraints. Directed edges in the graph are present whenever a node can talk to another node securely in the presence of eavesdroppers, which, in the model, is determined solely by the locations of the nodes and eavesdroppers. In the case of infinite networks, a critical parameter is the maximum density of eavesdroppers that can be accommodated while still guaranteeing an infinite component in the network, i.e., the percolation threshold. We focus on the case where the locations of the nodes and eavesdroppers are given by Poisson point processes, and present bounds for different types of percolation, including in-, out- and undirected percolation.     

广播网络的最佳源点集

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

On the Probability of Correct Selection in Ordinal Comparison over Dynamic Networks

We consider distributed ordinal comparison of selecting the best option which maximizes the average of local reward function values among available options in a dynamic network. Each node in the network knows only his reward function, and edge-connectivity across the nodes changes over time by Calafiore??s model. To estimate each option??s global reward function value, local samples for each option are generated at each node and those are iteratively mixed over the network by a weighted average of local estimates of instantaneous neighbors. Each node selects an option that achieves the maximum of the current global estimates as an estimate of the best option. We establish a lower bound on the probability of correct local-selection at any node, which uniformly converges over the nodes to a lower bound on the probability of correct global-selection by a virtual centralized node with the total available samples.     

A network-based approach for increasing discrimination in data envelopment analysis

Data envelopment analysis (DEA) is known to produce more than one efficient decision-making unit (DMU). This paper proposes a network-based approach for further increasing discrimination among these efficient DMUs. The approach treats the system under study as a directed and weighted network in which nodes represent DMUs and the direction and strength of the links represent the relative relationship among DMUs. In constructing the network, the observed node is set to point to its referent DMUs as suggested by DEA. The corresponding lambda values for these referent DMUs are taken as the strength of the network link. The network is weaved by not only the full input/output model, but also by models of all possible input/output combinations. Incorporating these models into the system basically introduces the merits of each DMU under various situations into the system and thus provides the key information for further discrimination. Once the network is constructed, the centrality concept commonly used in social network analysis—specifically, eigenvector centrality—is employed to rank the efficient DMUs. The network-based approach tends to rank high the DMUs that are not specialized and have balanced strengths.     

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

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

Application of modal analysis in assessing attack vulnerability of complex networks

In this paper we propose an alternative way to study robustness and vulnerability of complex networks, applying a modal analysis. The modal weights of the network nodes are considered as a measure for their busyness, which is further used for preferential removal of nodes and attack simulation. Analyses of the attack vulnerability are carried out for several generic graphs, generated according to ER and BA algorithms, as well as for some examples of manmade networks. It was found that a modal weight based attack causes significant disintegration of manmade networks by removing a small fraction of the busiest nodes, comparable to the one based on the node degree and betweenness centrality.     

国内外黄金现货价格联动波动复杂网络拓扑性质

为了研究国内外黄金现货价格联动性波动特征,选取2003年1月1日至2013年9月6日上海黄金交易所Au9999黄金现货收盘价与伦敦标准黄金现货的下午定盘价分别作为国内与国外黄金现货价格的样本数据.依据粗粒化方法,将Au9999与伦敦标准金价格的联动波动转化为由5个{P,O,M}三个字符构成的字符串,每一个字符串代表每5天的黄金现货价格联动波动模态,共产生106个模态.将模态作为节点,模态之间的转化为边,构建国内外黄金现货价格联动性波动复杂网络.对联动性复杂网络的点强度与强度分布、聚集系数、平均路径长度、中介中心性及凝集子群特征进行研究分析.结果表明:点强度值较大的前32个节点累积强度分布达到了92.05%,点强度与度分布、点强度与其等级均呈幂律分布;加权集聚系数与点强度之间并没有表现出良好的相关性,网络中存在14个小群簇;网络平均最短路径长度为7.668;节点中介性差异不太明显,前40个节点对整个网络的中介中心性贡献率为62.29%;8个节点的凝集子群有2个,8个节点以上的子群不存在.从网络结构拓扑性质角度验证了国内外黄金现货价格变化的复杂特征,这些对于掌握国内外黄金价格波动的内在规律和了解价格变化信息有一定指导意义,能够为我国黄金价格制定、风险投资和规避经济风险提供决策参考.     

“21世纪海上丝绸之路”沿线港口地位综合评价

本文基于复杂网络节点重要性分析方法,从海运网络分析的视角对“21世纪海上丝绸之路”沿线港口参与“一带一路”建设的地位进行评价。在收集海上丝绸之路沿线102个港口实际数据的基础上,构建海上丝绸之路海运网络拓扑结构图。通过对网络中港口节点的度中心性、接近中心性、中介中心性、特征向量中心性指标进行计算,结合熵权TOPSIS法综合得到港口地位的排序。结果表明新加坡港、上海港、巴生港在网络中具有很高的地位,且现有的复杂网络节点重要性排序方法存在局限,基于熵权TOPSIS法的综合评价得到的港口排序更符合实际发展需求。最后运用节点删除法对排序结果进一步分析,为中国港口参与“一带一路”建设提供参考与建议。     

Summing over a network without revealing summands

Consider a network in which each node possesses a secret member of a finite abelian group. In this paper we present a protocol by which the nodes can compute the sums of their secret elements without revealing them to each other. The security against discovery of the secret values as a result of conspiracies among nodes or compromise of channels between nodes is shown to depend on the connectivity of the graph defined by the network. Moreover, we are able to quantify exactly the amount of information revealed as a result of a conspiracy of a given set of nodes or compromise of a given set of channels.     

Optimal seamless self-assembly of files in linear networks

A file F is sited at one end (the root) of a path in some network. Each non-root node in the path is able to cache part or all of F, and each node may also have a client wanting to download F. Links between neighbors on the path have given transmission delays associated with them, but the delay from a node to its own client, if it has one, is zero. In the seamless, self-assembly paradigm all clients issue requests simultaneously at time 0, each starts to receive segments of F immediately, and continues to receive them until F is fully downloaded. The process must be implemented by means of a distributed self-assembly protocol which is unaware of network structure beyond links to immediate neighbors. We exhibit such a protocol, and show how to assign segments of F to the node caches in such a way that, no matter which nodes are chosen as clients, seamless self-assembly is realized and, simultaneously, the total cache size achieves a lower bound determined solely by the link delays. The paper concludes with a brief discussion of the many open problems arising in systems requiring seamless, or nearly seamless, self assembly of files.     

A cutting-plane algorithm for solving a weighted influence interdiction problem

We consider a two-stage defender-attacker game that takes place on a network, in which the attacker seeks to take control over (or “influence”) as many nodes as possible. The defender acts first in this game by protecting a subset of nodes that cannot be influenced by the attacker. With full knowledge of the defender’s action, the attacker can then influence an initial subset of unprotected nodes. The influence then spreads over a finite number of time stages, where an uninfluenced node becomes influenced at time t if a threshold number of its neighbors are influenced at time t?1. The attacker’s objective is to maximize the weighted number of nodes that are influenced over the time horizon, where the weights depend both on the node and on the time at which that is influenced. This defender-attacker game is especially difficult to optimize, because the attacker’s problem itself is NP-hard, which precludes a standard inner-dualization approach that is common in many interdiction studies. We provide three models for solving the attacker’s problem, and develop a tailored cutting-plane algorithm for solving the defender’s problem. We then demonstrate the computational efficacy of our proposed algorithms on a set of randomly generated instances.     

Location tracking in mobile ad hoc networks using particle filters

Mobile ad hoc networks (MANETs) are dynamic networks formed on-the-fly as mobile nodes move in and out of each others' transmission ranges. In general, the mobile ad hoc networking model makes no assumption that nodes know their own locations. However, recent research shows that location-awareness can be beneficial to fundamental tasks such as routing and energy-conservation. On the other hand, the cost and limited energy resources associated with common, low-cost mobile nodes prohibits them from carrying relatively expensive and power-hungry location-sensing devices such as GPS. This paper proposes a mechanism that allows non-GPS-equipped nodes in the network to derive their approximated locations from a limited number of GPS-equipped nodes. In our method, all nodes periodically broadcast their estimated location, in terms of a compressed particle filter distribution. Non-GPS nodes estimate the distance to their neighbors by measuring the received signal strength of incoming messages. A particle filter is then used to estimate the approximated location, along with a measure of confidence, from the sequence of distance estimates. Simulation studies show that our solution is capable of producing good estimates equal or better than the existing localization methods such as APS-Euclidean for the more difficult scenario when the network connectivity is low.