Emergence of scaling and assortative mixing through altruism

Many social networks, apart from displaying scale-free characteristics observed in some instances, possess another remarkable feature that distinguishes them from those that appear in biological and technological context—assortativity. However, little or no attention has been payed to the mechanism of assortativity in modeling these networks. Inspired by individuals’ altruistic behavior in sociology, we develop a model with a different growth mechanism called “altruistic attachment”, which can reproduce not only the power law degree distribution but degree correlations. We study in detail the statistical properties of our network model, which we also demonstrate striking differences with the BA model, and can portray real social networks more precisely.     

A game theory model of urban public traffic networks

We have studied urban public traffic networks from the viewpoint of complex networks and game theory. Firstly, we have empirically investigated an urban public traffic network in Beijing in 2003, and obtained its statistical properties. Then a simplified game theory model is proposed for simulating the evolution of the traffic network. The basic idea is that three network manipulators, passengers, an urban public traffic company, and a government traffic management agency, play games in a network evolution process. Each manipulator tries to build the traffic lines to magnify its “benefit”. Simulation results show a good qualitative agreement with the empirical results.     

The multi-agent Parrondo’s model based on the network evolution

A multi-agent Parrondo’s model is proposed in the paper. The model includes link A based on the rewiring mechanism (the network evolution) + game B (dependent on the spatial neighbors). Moreover, to produce the paradoxical effect and analyze the “agitating” effect of the network evolution, the dynamic processes of the network evolution + game B are studied. The simulation results and the theoretical analysis both show that the network evolution can make game B which is losing produce the winning paradoxical effect. Furthermore, we obtain the parameter space where the strong or weak Parrondo’s paradox occurs. Each size of the region of the parameter space is larger than the one in the available multi-agent Parrondo’s model of game A + game B. This result shows that the “agitating” effect of rewiring based on the network evolution is better than that of the zero-sum game between individuals.     

Modeling online social networks based on preferential linking

We study the phenomena of preferential linking in a large-scale evolving online social network and find that the linear preference holds for preferential creation,preferential acceptance,and preferential attachment.Based on the linear preference,we propose an analyzable model,which illustrates the mechanism of network growth and reproduces the process of network evolution.Our simulations demonstrate that the degree distribution of the network produced by the model is in good agreement with that of the real network.This work provides a possible bridge between the micro-mechanisms of network growth and the macrostructures of online social networks.     

“Antiferromagnetism” in social relations and Bonabeau model

We here present a fixed agents version of an original model of the emergence of hierarchies among social agents first introduced by Bonabeau et al. Having interactions occurring on a social network rather than among “walkers” does not drastically alter the dynamics. But it makes social structures more stable and give a clearer picture of the social organisation in a “mixed” regime, where finite ordered domains appear.     

A novel similarity measure for mining missing links in long-path networks

Network information mining is the study of the network topology, which may answer a large number of application-based questions towards the structural evolution and the function of a real system. The question can be related to how the real system evolves or how individuals interact with each other in social networks. Although the evolution of the real system may seem to be found regularly, capturing patterns on the whole process of evolution is not trivial. Link prediction is one of the most important technologies in network information mining, which can help us understand the evolution mechanism of real-life network. Link prediction aims to uncover missing links or quantify the likelihood of the emergence of nonexistent links from known network structures. Currently, widely existing methods of link prediction almost focus on short-path networks that usually have a myriad of close triangular structures. However, these algorithms on highly sparse or long-path networks have poor performance. Here, we propose a new index that is associated with the principles of structural equivalence and shortest path length (SESPL) to estimate the likelihood of link existence in long-path networks. Through a test of 548 real networks, we find that SESPL is more effective and efficient than other similarity-based predictors in long-path networks. Meanwhile, we also exploit the performance of SESPL predictor and of embedding-based approaches via machine learning techniques. The results show that the performance of SESPL can achieve a gain of 44.09% over GraphWave and 7.93% over Node2vec. Finally, according to the matrix of maximal information coefficient (MIC) between all the similarity-based predictors, SESPL is a new independent feature in the space of traditional similarity features.     

Rich-club and page-club coefficients for directed graphs

Rich-club and page-club coefficients and their null models are introduced for directed graphs. Null models allow for a quantitative discussion of the rich-club and page-club phenomena. These coefficients are computed for four directed real-world networks: Arxiv High Energy Physics paper citation network, Web network (released from Google), Citation network among US Patents, and email network from a EU research institution. The results show a high correlation between rich-club and page-club ordering. For journal paper citation network, we identify both rich-club and page-club ordering, showing that “elite” papers are cited by other “elite” papers. Google web network shows partial rich-club and page-club ordering up to some point and then a narrow declining of the corresponding normalized coefficients, indicating the lack of rich-club ordering and the lack of page-club ordering, i.e. high in-degree (PageRank) pages purposely avoid sharing links with other high in-degree (PageRank) pages. For UC patents citation network, we identify page-club and rich-club ordering providing a conclusion that “elite” patents are cited by other “elite” patents. Finally, for email communication network we show lack of both rich-club and page-club ordering. We construct an example of synthetic network showing page-club ordering and the lack of rich-club ordering.     

The role of syntax in complex networks: Local and global importance of verbs in a syntactic dependency network

Syntax of natural language has been the focus of linguistics for decades. The complex network theory, being one of new research tools, opens new perspectives on syntax properties of the language. Despite numerous partial achievements, some fundamental problems remain unsolved. Specifically, although statistical properties typical for complex networks can be observed in all syntactic networks, the impact of syntax itself on these properties is still unclear. The aim of the present study is to shed more light on the role of syntax in the syntactic network structure. In particular, we concentrate on the impact of the syntactic function of a verb in the sentence on the complex network structure. Verbs play the decisive role in the sentence structure (“local” importance). From this fact we hypothesize the importance of verbs in the complex network (“global” importance). The importance of verb in the complex network is assessed by the number of links which are directed from the node representing verb to other nodes in the network. Six languages (Catalan, Czech, Dutch, Hungarian, Italian, Portuguese) were used for testing the hypothesis.     

基于Sierpinski分形垫的确定性复杂网络演化模型研究

近年来,人们发现大量真实网络都表现出小世界和无尺度的特性,由此复杂网络演化模型成为学术界研究的热点问题.本文基于Sierpinski分形垫,通过迭代的方式构造了两个确定性增长的复杂网络模型,即小世界网络模型(S-DSWN)和无尺度网络模型(S-DSFN);其次,给出了确定性网络模型的迭代生成算法,解析计算了其主要拓扑特性,结果表明两个网络模型在度分布、集聚系数和网络直径等结构特性方面与许多现实网络相符合;最后,提出了一个确定性的统一模型(S-DUM),将S-DSWN与S-DSFN纳入到一个框架之下,为复杂网络的相关研究提供理论基础.特别地,发现这些网络模型都是极大平面图.     

Studies on controllability of directed networks with extremal optimization

Almost all natural, social and man-made-engineered systems can be represented by a complex network to describe their dynamic behaviors. To make a real-world complex network controllable with its desired topology, the study on network controllability has been one of the most critical and attractive subjects for both network and control communities. In this paper, based on a given directed–weighted network with both state and control nodes, a novel optimization tool with extremal dynamics to generate an optimal network topology with minimum control nodes and complete controllability under Kalman’s rank condition has been developed. The experimental results on a number of popular benchmark networks show the proposed tool is effective to identify the minimum control nodes which are sufficient to guide the whole network’s dynamics and provide the evolution of network topology during the optimization process. We also find the conclusion: “the sparse networks need more control nodes than the dense, and the homogeneous networks need fewer control nodes compared to the heterogeneous” (Liu et al., 2011  [18]), is also applicable to network complete controllability. These findings help us to understand the network dynamics and make a real-world network under the desired control. Moreover, compared with the relevant research results on structural controllability with minimum driver nodes, the proposed solution methodology may also be applied to other constrained network optimization problems beyond complete controllability with minimum control nodes.     

Model updating via weighted reference basis with connectivity constraints

The paper considers the problem of updating an analytical model from experimental data using the reference basis approach. In the general framework of the reference basis method, certain quantities, e.g., natural frequencies or modeshapes, are considered to be completely accurate and the others are updated by solving a constrained optimization problem. However, the underlying structure, known as connectivity, existing in the model is not preserved, and the method is not suited for parametric updating. In this paper, a method for introducing connectivity constraints into reference basis, while maintaining its advantages, is presented. It brings the reference basis method closer to a broad class of updating methods that use parametric updating. The notions of “connectivity cost” and “parameterization cost” are defined and used to obtain the best model for a given parameterization and to compare the outcomes of different parameterizations.     

Toward cell circuitry: Topological analysis of enzyme reaction networks via reaction route graphs

The first step toward developing complete cell circuitry is to build quantitative networks for enzyme reactions. The conventional King-Altman-Hill (KAH) algorithm for topological analysis of enzyme networks, adapted from electrical networks, is based on “Reaction Graphs” that, unlike electrical circuits, are not quantitative, being straightforward renderings of conventional schematics of reaction mechanisms. Therefore, we propose the use of “Reaction Route (RR) Graphs” instead, as a more suitable graph-theoretical representation for topological analysis of enzyme reaction networks. The RR Graphs are drawn such that they are not only useful for visualizing the various reaction routes or pathways, but unlike Reaction Graphs possess network properties consistent with requisite kinetic, mass balance, and thermodynamic constraints. Therefore, they are better than the conventional Reaction Graphs for topological representation and analysis of enzyme reactions, both via the KAH methodology as well as via numerical matrix inversion. The difference between the two is highlighted based on the example of a single enzyme reaction network for the conversion of 7,8-dihydrofolate and NADPH into 5,6,7,8-tetrahydrofolate and NADP⁺, catalyzed by the enzyme dihydrofolate reductase.     

Fronts and bumps in spatially extended Kuramoto networks

We consider moving fronts and stationary “bumps” in networks of non-locally coupled phase oscillators. Fronts connect regions of high local synchrony with regions of complete asynchrony, while bumps consist of spatially-localised regions of partially-synchronous oscillators surrounded by complete asynchrony. Using the Ott-Antonsen ansatz we derive non-local differential equations which describe the network dynamics in the continuum limit. Front and bump solutions of these equations are studied by either “freezing” them in a travelling coordinate frame or analysing them as homoclinic or heteroclinic orbits. Numerical continuation is used to determine parameter regions in which such solutions exist and are stable.     

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

本文构造了一个基于在线社交网络的信息传播模型.该模型考虑了节点度和传播机理的影响,结合复杂网络和传染病动力学理论,进一步建立了动力学演化方程组.该方程组刻画了不同类型节点随着时间的演化关系,反映了传播动力学过程受到网络拓扑结构和传播机理的影响.本文模拟了在线社交网络中的信息传播过程,并分析了不同类型节点在网络中的行为规律.仿真结果表明:由于在线社交网络的高度连通性,信息在网络中传播的门槛几乎为零;初始传播节点的度越大,信息越容易在网络中迅速传播;中心节点具有较大的社会影响力;具有不同度数的节点在网络中的变 关键词： 在线社交网络 信息传播 微分方程 传染病动力学     

Networks of strong ties

Social networks transmitting covert or sensitive information cannot use all ties for this purpose. Rather, they can only use a subset of ties that are strong enough to be “trusted”. This paper addresses whether it is still possible, under this restriction, for information to be transmitted widely and rapidly in social networks. We use transitivity as evidence of strong ties, requiring one or more shared contacts in order to count an edge as strong. We examine the effect of removing all non-transitive ties in two real social network data sets, imposing varying thresholds in the number of shared contacts. We observe that transitive ties occupy a large portion of the network and that removing all other ties, while causing some individuals to become disconnected, preserves the majority of the giant connected component. Furthermore, the average shortest path, important for the rapid diffusion of information, increases only slightly relative to the original network. We also evaluate the cost of forming transitive ties by modeling a random graph composed entirely of closed triads and comparing its connectivity and average shortest path with the equivalent Erdös–Renyi random graph. Both the empirical study and random model point to a robustness of strong ties with respect to the connectivity and small world property of social networks.     

The influence of tie strength on evolutionary games on networks: An empirical investigation

Extending previous work on unweighted networks, we present here a systematic numerical investigation of standard evolutionary games on weighted networks. In the absence of any reliable model for generating weighted social networks, we attribute weights to links in a few ways supported by empirical data ranging from totally uncorrelated to weighted bipartite networks. The results of the extensive simulation work on standard complex network models show that, except in a case that does not seem to be common in social networks, taking the tie strength into account does not change in a radical manner the long-run steady-state behavior of the studied games. Besides model networks, we also included a real-life case drawn from a coauthorship network. In this case also, taking the weights into account only changes the results slightly with respect to the raw unweighted graph, although to draw more reliable conclusions on real social networks many more cases should be studied as these weighted networks become available.     

A network of two-Chinese-character compound words in the Japanese language

Some statistical properties of a network of two-Chinese-character compound words in the Japanese language are reported. In this network, a node represents a Chinese character and an edge represents a two-Chinese-character compound word. It is found that this network has properties of being “small-world” and “scale-free”. A network formed by only Chinese characters for common use (joyo-kanji in Japanese), which is regarded as a subclass of the original network, also has the small-world property. However, a degree distribution of the network exhibits no clear power law. In order to reproduce the disappearance of the power-law property, a model for a selecting process of the Chinese characters for common use is proposed.     

The dynamics of chimera states in heterogeneous Kuramoto networks

We study a variety of mixed synchronous/incoherent (“chimera”) states in several heterogeneous networks of coupled phase oscillators. For each network, the recently-discovered Ott-Antonsen ansatz is used to reduce the number of variables in the partial differential equation (PDE) governing the evolution of the probability density function by one, resulting in a time-evolution PDE for a variable with as many spatial dimensions as the network. Bifurcation analysis is performed on the steady states of these PDEs. The results emphasise the commonality of the dynamics of the different networks, and provide stability information that was previously inferred.     

Is the topology of the Internet network really fit to sustain its function?

The Internet is one of the most interesting realizations of a “complex” network. As a non-supervised growing object, it allows the study of the selective pressure which drives the network to assume its current structure. The DIMES and the ROUTEVIEWS projects are ongoing projects aimed at evaluating the topological structure of the Internet (at the Autonomous System or AS grain-level) on the basis of different types of measurements. The topological analysis of the networks produced by the two projects has allowed us to infer a growth mechanism which has been used to build up synthetic networks with similar properties. These networks have been used as test-beds for the implementation of a model of traffic dynamics, with the aim of assessing the ability of the Internet’s topology to support the basic actions for data traffic handling. Results have been compared with those obtained by using a random network of similar size. The effects of some structural perturbations (arcs and nodes’ removal, traffic localization) have been also evaluated in terms of the induced variations of the network’s efficiency. The resulting scenario is consistent with the hypothesis that the structure of the Internet is only partially fit to host communication processes and that the intelligence of the TCP/IP protocol is partly needed to overcome some “structural” deficiencies.     

Communities in Italian corporate networks

The community structure of two real-world financial networks, namely the board network and the ownership network of the firms of the Italian Stock Exchange, is analyzed by means of the maximum modularity approach. The main result is that both networks exhibit a strong community structure and, moreover, that the two structures overlap significantly. This is due to a number of reasons, including the existence of pyramidal groups and directors serving in several boards. Overall, this means that the “small world” of listed companies is actually split into well identifiable “continents” (i.e., the communities).