动态复杂网络中节点影响力的研究进展

节点影响力的识别和预测具有重要的理论意义和应用价值,是复杂网络的热点研究领域.目前大多数研究方法都是针对静态网络或动态网络某一时刻的快照进行的,然而在实际应用场景中,社会、生物、信息、技术等复杂网络都是动态演化的.因此在动态复杂网络中评估节点影响力以及预测节点未来影响力,特别是在网络结构变化之前的预测更具意义.本文系统地总结了动态复杂网络中节点影响力算法面临的三类挑战,即在增长网络中,节点影响力算法的计算复杂性和时间偏见;网络实时动态演化时,节点影响力算法的适应性;网络结构微扰或突变时,节点影响力算法的鲁棒性,以及利用网络结构演变阐释经济复杂性涌现的问题.最后总结了这一研究方向几个待解决的问题并指出未来可能的发展方向.     

Elucidation of conserved long-range interaction networks in proteins and their significance in determining protein topology

Investigations into the nature of sequence and structural conservation underlying protein folds have recently yielded profound insights into the mechanism of protein folding and stability. Combining this avenue of research with principles being pioneered in the field of network science holds the promise to further extend the boundaries of our knowledge. In this report we propose that critical determinants of a protein's native topology are encoded by a conserved network of interactions between amino acids from geographically important positions. This hypothesis is based on the novel elucidation of a conserved network of long-range interactions within a set of proteins that share a Greek-key topology and similar chain length, but differ in secondary structure composition, function and sequence. Exploratory macromolecular simulations using the conserved networks as constraints were successful in generating the gross native-like topology from a random linear coil for each of the model proteins. The results indicate that the conserved network contains governing features and supports the idea that the geographical location of these residue interactions is a pivotal feature underlying their conservation. The partially folded model proteins also display a clear scale-free distribution of long-range interactions. To further test the hypothesis, the network parameter betweeness-centrality was calculated for the protein structure networks of our model proteins and highlights two structural elements as particularly vital to the structural stability of the network topology.     

Social networks: Ideas for future research from the vantage point of political science

In this short piece, Bunce and Csanadi draw upon their expertise in political science and political economy to offer some observations about the analysis of social networks. Using both examples and questions they highlight the importance of structural variations in networks, including differences in the motivations behind network formation; the subsequent development of networks, including extension, contraction and duration; and the effects of individual decision-makers on network dynamics and, at the same time, the effects of network structure and dynamics on individual decision-makers.     

Principle of structural equation modeling for exploring functional interactivity within a putative network of interconnected brain areas

Functional neuroimaging first allowed researchers to describe the functional segregation of regionally activated areas during a variety of experimental tasks. More recently, functional integration studies have described how these functionally specialized areas, interact within a highly distributed neural network. When applied to the field of neurosciences, structural equation modeling (SEM) uses theoretical and/or empirical hypotheses to estimate the effects of an experimental task within a putative network. SEM represents a linear technique for multivariate analysis of neuroimaging data and has been developed to simultaneously examine ratios of multiple causality in an experimental design; the method attempts to explain a covariance structure within an anatomical constrained model. This method, when combined with the concept of effective connectivity, can provide information on the strength and direction of the functional interactions that take place between identified brain regions of a putative network.     

Quantifying information loss on chaotic attractors through recurrence networks

We propose an entropy measure for the analysis of chaotic attractors through recurrence networks which are un-weighted and un-directed complex networks constructed from time series of dynamical systems using specific criteria. We show that the proposed measure converges to a constant value with increase in the number of data points on the attractor (or the number of nodes on the network) and the embedding dimension used for the construction of the network, and clearly distinguishes between the recurrence network from chaotic time series and white noise. Since the measure is characteristic to the network topology, it can be used to quantify the information loss associated with the structural change of a chaotic attractor in terms of the difference in the link density of the corresponding recurrence networks. We also indicate some practical applications of the proposed measure in the recurrence analysis of chaotic attractors as well as the relevance of the proposed measure in the context of the general theory of complex networks.     

Evolutionary design of oscillatory genetic networks

The present study is devoted to the design and statistical investigations of dynamical gene expression networks. In our model problem, we aim to design genetic networks which would exhibit stable periodic oscillations with a prescribed temporal period. While no rational solution of this problem is available, we show that it can be effectively solved by running a computer evolution of the network models. In this process, structural rewiring mutations are applied to the networks with inhibitory interactions between genes and the evolving networks are selected depending on whether, after a mutation, they closer approach the targeted dynamics. We show that, by using this method, networks with required oscillation periods, varying by up to three orders of magnitude, can be constructed by changing the architecture of regulatory connections between the genes. Statistical properties of designed networks, including motif distributions and Laplacian spectra, are considered.     

Synchronization in complex networks

Synchronization processes in populations of locally interacting elements are the focus of intense research in physical, biological, chemical, technological and social systems. The many efforts devoted to understanding synchronization phenomena in natural systems now take advantage of the recent theory of complex networks. In this review, we report the advances in the comprehension of synchronization phenomena when oscillating elements are constrained to interact in a complex network topology. We also take an overview of the new emergent features coming out from the interplay between the structure and the function of the underlying patterns of connections. Extensive numerical work as well as analytical approaches to the problem are presented. Finally, we review several applications of synchronization in complex networks to different disciplines: biological systems and neuroscience, engineering and computer science, and economy and social sciences.     

Approaching human language with complex networks

The interest in modeling and analyzing human language with complex networks is on the rise in recent years and a considerable body of research in this area has already been accumulated. We survey three major lines of linguistic research from the complex network approach: 1) characterization of human language as a multi-level system with complex network analysis; 2) linguistic typological research with the application of linguistic networks and their quantitative measures; and 3) relationships between the system-level complexity of human language (determined by the topology of linguistic networks) and microscopic linguistic (e.g., syntactic) features (as the traditional concern of linguistics). We show that the models and quantitative tools of complex networks, when exploited properly, can constitute an operational methodology for linguistic inquiry, which contributes to the understanding of human language and the development of linguistics. We conclude our review with suggestions for future linguistic research from the complex network approach: 1) relationships between the system-level complexity of human language and microscopic linguistic features; 2) expansion of research scope from the global properties to other levels of granularity of linguistic networks; and 3) combination of linguistic network analysis with other quantitative studies of language (such as quantitative linguistics).     

Influence of a network structure on the network effect in the communication service market

In this study, we analyze the network effect in a model of a personal communication market, by using a multi-agent based simulation approach. We introduce into the simulation model complex network structures as the interaction patterns of agents. With complex network models, we investigate the dynamics of a market in which two providers are competing. We also examine the structure of networks that affect the complex behavior of the market. By a series of simulations, we show that the structural properties of complex networks, such as the clustering coefficient and degree correlation, have a major influence on the dynamics of the market. We find that the network effect is increased if the interaction pattern of agents is characterized by a high clustering coefficient, or a positive degree correlation. We also discuss a suitable model of the interaction pattern for reproducing market dynamics in the real world, by performing simulations using real data of a social network.     

Link prediction in complex networks: A survey

Link prediction in complex networks has attracted increasing attention from both physical and computer science communities. The algorithms can be used to extract missing information, identify spurious interactions, evaluate network evolving mechanisms, and so on. This article summaries recent progress about link prediction algorithms, emphasizing on the contributions from physical perspectives and approaches, such as the random-walk-based methods and the maximum likelihood methods. We also introduce three typical applications: reconstruction of networks, evaluation of network evolving mechanism and classification of partially labeled networks. Finally, we introduce some applications and outline future challenges of link prediction algorithms.     

Drivers of structural features in gene regulatory networks: From biophysical constraints to biological function

Living cells can maintain their internal states, react to changing environments, grow, differentiate, divide, etc. All these processes are tightly controlled by what can be called a regulatory program. The logic of the underlying control can sometimes be guessed at by examining the network of influences amongst genetic components. Some associated gene regulatory networks have been studied in prokaryotes and eukaryotes, unveiling various structural features ranging from broad distributions of out-degrees to recurrent “motifs”, that is small subgraphs having a specific pattern of interactions. To understand what factors may be driving such structuring, a number of groups have introduced frameworks to model the dynamics of gene regulatory networks. In that context, we review here such in silico approaches and show how selection for phenotypes, i.e., network function, can shape network structure.     

Optimization of controllability and robustness of complex networks by edge directionality

Recently, controllability of complex networks has attracted enormous attention invarious fields of science and engineering. How to optimize structural controllability hasalso become a significant issue. Previous studies have shown that an appropriatedirectional assignment can improve structural controllability; however, the evolution ofthe structural controllability of complex networks under attacks and cascading has alwaysbeen ignored. To address this problem, this study proposes a new edge orientation method(NEOM) based on residual degree that changes the link direction while conserving topologyand directionality. By comparing the results with those of previous methods in two randomgraph models and several realistic networks, our proposed approach is demonstrated to bean effective and competitive method for improving the structural controllability ofcomplex networks. Moreover, numerical simulations show that our method is near-optimal inoptimizing structural controllability. Strikingly, compared to the original network, ourmethod maintains the structural controllability of the network under attacks andcascading, indicating that the NEOM can also enhance the robustness of controllability ofnetworks. These results alter the view of the nature of controllability in complexnetworks, change the understanding of structural controllability and affect the design ofnetwork models to control such networks.     

Reconstruction of a random phase dynamics network from observations

We consider networks of coupled phase oscillators of different complexity: Kuramoto–Daido-type networks, generalized Winfree networks, and hypernetworks with triple interactions. For these setups an inverse problem of reconstruction of the network connections and of the coupling function from the observations of the phase dynamics is addressed. We show how a reconstruction based on the minimization of the squared error can be implemented in all these cases. Examples include random networks with full disorder both in the connections and in the coupling functions, as well as networks where the coupling functions are taken from experimental data of electrochemical oscillators. The method can be directly applied to asynchronous dynamics of units, while in the case of synchrony, additional phase resettings are necessary for reconstruction.     

复杂网络可控性研究现状综述

控制复杂系统是人们对复杂系统模型结构及相关动力学进行研究的最终目标, 反映人们对复杂系统的认识能力. 近年来, 通过控制理论和复杂性科学相结合,复杂网络可控性的研究引起了人们的广泛关注. 在过去的几年内, 来自国内外不同领域的研究人员从不同的角度对复杂网络可控性进行了深入的分析研究, 取得了丰硕的成果. 本文重点讨论了复杂网络的结构可控性研究进展, 详细介绍了基于最大匹配方法的复杂网络结构可控性分析框架, 综述了自2011年以来复杂网络可控性的相关研究成果, 具体论述了不同类型的可控性、可控性与网络拓扑结构统计特征的关联、基于可控性的网络及节点度量、控制的鲁棒性和可控性的相关优化方法. 最后, 对网络可控性未来的研究动态进行了展望, 有助于国内同行开展网络可控性的相关研究.     

Urban road network evolution mechanism based on the ‘direction preferred connection’ and ‘degree constraint’

The urban road network is a complex system that exhibits the properties of self-organization and emergence. Recent theoretical and empirical studies have mainly focused on the structural properties of the urban road networks. This research concentrates on some important parameters such as degree, average degree, meshedness coefficient, betweeness, etc. These parameters of the real road network exhibit specific statistical properties. Some studies show that perhaps these specific statistical properties are caused by a compromise mechanism of the formation of a minimum spanning tree and the greedy triangulation. Inspired by these results, we propose a principle to construct the network (we call it a MG network in this paper) whose structure is located between the minimum spanning tree and the greedy triangulation at first. The structural properties of the MG network are analyzed. We find the formation mechanism of the MG network cannot explain the urban road network evolution well. Then, based on the formation mechanism of the MG network, we add the ‘direction preferred connection’ and ‘degree constraint’ principles to the urban road network evolution simulation process. The result of the simulation network turns out to be a planar network that is in accordance with reality. Compared with the real road network’s structural properties, we find the simulation results are so consistent with it. It indicates the validation of the model and also demonstrates perhaps the ‘direction preferred connection’ and ‘degree constraint’ principle can explain the urban road network evolution better.     

Complex network analysis of water distribution systems

This paper explores a variety of strategies for understanding the formation, structure, efficiency, and vulnerability of water distribution networks. Water supply systems are studied as spatially organized networks for which the practical applications of abstract evaluation methods are critically evaluated. Empirical data from benchmark networks are used to study the interplay between network structure and operational efficiency, reliability, and robustness. Structural measurements are undertaken to quantify properties such as redundancy and optimal-connectivity, herein proposed as constraints in network design optimization problems. The role of the supply demand structure toward system efficiency is studied, and an assessment of the vulnerability to failures based on the disconnection of nodes from the source(s) is undertaken. The absence of conventional degree-based hubs (observed through uncorrelated nonheterogeneous sparse topologies) prompts an alternative approach to studying structural vulnerability based on the identification of network cut-sets and optimal-connectivity invariants. A discussion on the scope, limitations, and possible future directions of this research is provided.     

Evaluation of network robustness using a node tearing algorithm

Until recently the study of failure and vulnerability in complex networks focused on the role of high degree nodes, and the relationship between their removal and network connectivity. Recent evidence suggested that in some network configurations, the removal of lower degree nodes can also cause network fragmentation. We present a disassembling algorithm that identifies nodes that are core to network connectivity. The algorithm is based on network tearing in which communities are defined and used to construct a hierarchical structure. Cut-nodes, which are located at the boundaries of the communities, are the key interest. Their importance in the overall network connectivity is characterized by their participation with neighbouring communities in each level of the hierarchy. We examine the impact of these cut-nodes by studying the change in size of the giant component, local and global efficiencies, and how the algorithm can be combined with other community detection methods to reveal the finer internal structure within a community.     

Mutually-antagonistic interactions in baseball networks

We formulate the head-to-head matchups between Major League Baseball pitchers and batters from 1954 to 2008 as a bipartite network of mutually-antagonistic interactions. We consider both the full network and single-season networks, which exhibit structural changes over time. We find interesting structure in the networks and examine their sensitivity to baseball’s rule changes. We then study a biased random walk on the matchup networks as a simple and transparent way to (1) compare the performance of players who competed under different conditions and (2) include information about which particular players a given player has faced. We find that a player’s position in the network does not correlate with his placement in the random walker ranking. However, network position does have a substantial effect on the robustness of ranking placement to changes in head-to-head matchups.     

面向结构洞的复杂网络关键节点排序

复杂网络中的结构洞节点对于信息传播具有重要作用, 现有关键节点排序方法多数没有兼顾结构洞节点和其他类型的关键节点进行排序. 本文根据结构洞理论与关键节点排序相关研究选取了网络约束系数、介数中心性、等级度、效率、网络规模、PageRank值以及聚类系数7个度量指标, 将基于ListNet的排序学习方法引入到复杂网络的关键节点排序问题中, 融合7个度量指标, 构建了一个能够综合评价面向结构洞节点的关键节点排序方法. 采用模拟网络和实际复杂网络进行了大量实验, 人工标准试验结果表明本文排序方法能够综合考虑结构洞节点和核心节点, 关键节点排序与人工排序结果具有较高的一致性. SIR传播模型评估实验结果表明由本文选择TOP-K节点发起的传播能够在较短的传播时间内达到最大的传播范围.     

Networks and emotion-driven user communities at popular blogs

Online communications at web portals represents technology-mediated user interactions, leading to massive data and potentially new techno-social phenomena not seen in real social mixing. Apart from being dynamically driven, the user interactions via posts is indirect, suggesting the importance of the contents of the posted material. We present a systematic way to study Blog data by combined approaches of physics of complex networks and computer science methods of text analysis. We are mapping the Blog data onto a bipartite network where users and posts with comments are two natural partitions. With the machine learning methods we classify the texts of posts and comments for their emotional contents as positive or negative, or otherwise objective (neutral). Using the spectral methods of weighted bipartite graphs, we identify topological communities featuring the users clustered around certain popular posts, and underly the role of emotional contents in the emergence and evolution of these communities.