PhysarumSpreader: A New Bio-Inspired Methodology for Identifying Influential Spreaders in Complex Networks

Identifying influential spreaders in networks, which contributes to optimizing the use of available resources and efficient spreading of information, is of great theoretical significance and practical value. A random-walk-based algorithm LeaderRank has been shown as an effective and efficient method in recognizing leaders in social network, which even outperforms the well-known PageRank method. As LeaderRank is initially developed for binary directed networks, further extensions should be studied in weighted networks. In this paper, a generalized algorithm PhysarumSpreader is proposed by combining LeaderRank with a positive feedback mechanism inspired from an amoeboid organism called Physarum Polycephalum. By taking edge weights into consideration and adding the positive feedback mechanism, PhysarumSpreader is applicable in both directed and undirected networks with weights. By taking two real networks for examples, the effectiveness of the proposed method is demonstrated by comparing with other standard centrality measures.     

A Novel Top-k Strategy for Influence Maximization in Complex Networks with Community Structure

In complex networks, it is of great theoretical and practical significance to identify a set of critical spreaders which help to control the spreading process. Some classic methods are proposed to identify multiple spreaders. However, they sometimes have limitations for the networks with community structure because many chosen spreaders may be clustered in a community. In this paper, we suggest a novel method to identify multiple spreaders from communities in a balanced way. The network is first divided into a great many super nodes and then k spreaders are selected from these super nodes. Experimental results on real and synthetic networks with community structure show that our method outperforms the classic methods for degree centrality, k-core and ClusterRank in most cases.     

Disease spread in small-size directed networks: Epidemic threshold, correlation between links to and from nodes, and clustering

Network epidemiology has mainly focused on large-scale complex networks. It is unclear whether findings of these investigations also apply to networks of small size. This knowledge gap is of relevance for many biological applications, including meta-communities, plant–pollinator interactions and the spread of the oomycete pathogen Phytophthora ramorum in networks of plant nurseries. Moreover, many small-size biological networks are inherently asymmetrical and thus cannot be realistically modelled with undirected networks. We modelled disease spread and establishment in directed networks of 100 and 500 nodes at four levels of connectance in six network structures (local, small-world, random, one-way, uncorrelated, and two-way scale-free networks). The model was based on the probability of infection persistence in a node and of infection transmission between connected nodes. Regardless of the size of the network, the epidemic threshold did not depend on the starting node of infection but was negatively related to the correlation coefficient between in- and out-degree for all structures, unless networks were sparsely connected. In this case clustering played a significant role. For small-size scale-free directed networks to have a lower epidemic threshold than other network structures, there needs to be a positive correlation between number of links to and from nodes. When this correlation is negative (one-way scale-free networks), the epidemic threshold for small-size networks can be higher than in non-scale-free networks. Clustering does not necessarily have an influence on the epidemic threshold if connectance is kept constant. Analyses of the influence of the clustering on the epidemic threshold in directed networks can also be spurious if they do not consider simultaneously the effect of the correlation coefficient between in- and out-degree.     

A fast layout algorithm for protein interaction networks

MOTIVATION: Graph drawing algorithms are often used for visualizing relational information, but a naive implementation of a graph drawing algorithm encounters real difficulties when drawing large-scale graphs such as protein interaction networks. RESULTS: We have developed a new, extremely fast layout algorithm for visualizing large-scale protein interaction networks in the three-dimensional space. The algorithm (1) first finds a layout of connected components of an entire network, (2) finds a global layout of nodes with respect to pivot nodes within a connected component and (3) refines the local layout of each connected component by first relocating midnodes with respect to their cutvertices and direct neighbors of the cutvertices and then by relocating all nodes with respect to their neighbors within distance 2. Advantages of this algorithm over classical graph drawing methods include: (1) it is an order of magnitude faster, (2) it can directly visualize data from protein interaction databases and (3) it provides several abstraction and comparison operations for effectively analyzing large-scale protein interaction networks. AVAILABILITY: http://wilab.inha.ac.kr/interviewer/     

Coevolution of Quantum and Classical Strategies on Evolving Random Networks

We study the coevolution of quantum and classical strategies on weighted and directed random networks in the realm of the prisoner’s dilemma game. During the evolution, agents can break and rewire their links with the aim of maximizing payoffs, and they can also adjust the weights to indicate preferences, either positive or negative, towards their neighbors. The network structure itself is thus also subject to evolution. Importantly, the directionality of links does not affect the accumulation of payoffs nor the strategy transfers, but serves only to designate the owner of each particular link and with it the right to adjust the link as needed. We show that quantum strategies outperform classical strategies, and that the critical temptation to defect at which cooperative behavior can be maintained rises, if the network structure is updated frequently. Punishing neighbors by reducing the weights of their links also plays an important role in maintaining cooperation under adverse conditions. We find that the self-organization of the initially random network structure, driven by the evolutionary competition between quantum and classical strategies, leads to the spontaneous emergence of small average path length and a large clustering coefficient.     

Community Size Effects on Epidemic Spreading in Multiplex Social Networks

The dynamical process of epidemic spreading has drawn much attention of the complex network community. In the network paradigm, diseases spread from one person to another through the social ties amongst the population. There are a variety of factors that govern the processes of disease spreading on the networks. A common but not negligible factor is people’s reaction to the outbreak of epidemics. Such reaction can be related information dissemination or self-protection. In this work, we explore the interactions between disease spreading and population response in terms of information diffusion and individuals’ alertness. We model the system by mapping multiplex networks into two-layer networks and incorporating individuals’ risk awareness, on the assumption that their response to the disease spreading depends on the size of the community they belong to. By comparing the final incidence of diseases in multiplex networks, we find that there is considerable mitigation of diseases spreading for full phase of spreading speed when individuals’ protection responses are introduced. Interestingly, the degree of community overlap between the two layers is found to be critical factor that affects the final incidence. We also analyze the consequences of the epidemic incidence in communities with different sizes and the impacts of community overlap between two layers. Specifically, as the diseases information makes individuals alert and take measures to prevent the diseases, the effective protection is more striking in small community. These phenomena can be explained by the multiplexity of the networked system and the competition between two spreading processes.     

Leaders in social networks, the Delicious case

Finding pertinent information is not limited to search engines. Online communities can amplify the influence of a small number of power users for the benefit of all other users. Users' information foraging in depth and breadth can be greatly enhanced by choosing suitable leaders. For instance in delicious.com, users subscribe to leaders' collection which lead to a deeper and wider reach not achievable with search engines. To consolidate such collective search, it is essential to utilize the leadership topology and identify influential users. Google's PageRank, as a successful search algorithm in the World Wide Web, turns out to be less effective in networks of people. We thus devise an adaptive and parameter-free algorithm, the LeaderRank, to quantify user influence. We show that LeaderRank outperforms PageRank in terms of ranking effectiveness, as well as robustness against manipulations and noisy data. These results suggest that leaders who are aware of their clout may reinforce the development of social networks, and thus the power of collective search.     

Directed Network Motifs in Alzheimer’s Disease and Mild Cognitive Impairment

Directed network motifs are the building blocks of complex networks, such as human brain networks, and capture deep connectivity information that is not contained in standard network measures. In this paper we present the first application of directed network motifs in vivo to human brain networks, utilizing recently developed directed progression networks which are built upon rates of cortical thickness changes between brain regions. This is in contrast to previous studies which have relied on simulations and in vitro analysis of non-human brains. We show that frequencies of specific directed network motifs can be used to distinguish between patients with Alzheimer’s disease (AD) and normal control (NC) subjects. Especially interesting from a clinical standpoint, these motif frequencies can also distinguish between subjects with mild cognitive impairment who remained stable over three years (MCI) and those who converted to AD (CONV). Furthermore, we find that the entropy of the distribution of directed network motifs increased from MCI to CONV to AD, implying that the distribution of pathology is more structured in MCI but becomes less so as it progresses to CONV and further to AD. Thus, directed network motifs frequencies and distributional properties provide new insights into the progression of Alzheimer’s disease as well as new imaging markers for distinguishing between normal controls, stable mild cognitive impairment, MCI converters and Alzheimer’s disease.     

Emergence of Blind Areas in Information Spreading

Recently, contagion-based (disease, information, etc.) spreading on social networks has been extensively studied. In this paper, other than traditional full interaction, we propose a partial interaction based spreading model, considering that the informed individuals would transmit information to only a certain fraction of their neighbors due to the transmission ability in real-world social networks. Simulation results on three representative networks (BA, ER, WS) indicate that the spreading efficiency is highly correlated with the network heterogeneity. In addition, a special phenomenon, namely Information Blind Areas where the network is separated by several information-unreachable clusters, will emerge from the spreading process. Furthermore, we also find that the size distribution of such information blind areas obeys power-law-like distribution, which has very similar exponent with that of site percolation. Detailed analyses show that the critical value is decreasing along with the network heterogeneity for the spreading process, which is complete the contrary to that of random selection. Moreover, the critical value in the latter process is also larger than that of the former for the same network. Those findings might shed some lights in in-depth understanding the effect of network properties on information spreading.     

Correlation Networks from Flows. The Case of Forced and Time-Dependent Advection-Diffusion Dynamics

Complex network theory provides an elegant and powerful framework to statistically investigate different types of systems such as society, brain or the structure of local and long-range dynamical interrelationships in the climate system. Network links in climate networks typically imply information, mass or energy exchange. However, the specific connection between oceanic or atmospheric flows and the climate network’s structure is still unclear. We propose a theoretical approach for verifying relations between the correlation matrix and the climate network measures, generalizing previous studies and overcoming the restriction to stationary flows. Our methods are developed for correlations of a scalar quantity (temperature, for example) which satisfies an advection-diffusion dynamics in the presence of forcing and dissipation. Our approach reveals that correlation networks are not sensitive to steady sources and sinks and the profound impact of the signal decay rate on the network topology. We illustrate our results with calculations of degree and clustering for a meandering flow resembling a geophysical ocean jet.     

Identification of Important Nodes in Directed Biological Networks: A Network Motif Approach

Identification of important nodes in complex networks has attracted an increasing attention over the last decade. Various measures have been proposed to characterize the importance of nodes in complex networks, such as the degree, betweenness and PageRank. Different measures consider different aspects of complex networks. Although there are numerous results reported on undirected complex networks, few results have been reported on directed biological networks. Based on network motifs and principal component analysis (PCA), this paper aims at introducing a new measure to characterize node importance in directed biological networks. Investigations on five real-world biological networks indicate that the proposed method can robustly identify actually important nodes in different networks, such as finding command interneurons, global regulators and non-hub but evolutionary conserved actually important nodes in biological networks. Receiver Operating Characteristic (ROC) curves for the five networks indicate remarkable prediction accuracy of the proposed measure. The proposed index provides an alternative complex network metric. Potential implications of the related investigations include identifying network control and regulation targets, biological networks modeling and analysis, as well as networked medicine.     

Motif-Role-Fingerprints: The Building-Blocks of Motifs,Clustering-Coefficients and Transitivities in Directed Networks

Complex networks are frequently characterized by metrics for which particular subgraphs are counted. One statistic from this category, which we refer to as motif-role fingerprints, differs from global subgraph counts in that the number of subgraphs in which each node participates is counted. As with global subgraph counts, it can be important to distinguish between motif-role fingerprints that are ‘structural’ (induced subgraphs) and ‘functional’ (partial subgraphs). Here we show mathematically that a vector of all functional motif-role fingerprints can readily be obtained from an arbitrary directed adjacency matrix, and then converted to structural motif-role fingerprints by multiplying that vector by a specific invertible conversion matrix. This result demonstrates that a unique structural motif-role fingerprint exists for any given functional motif-role fingerprint. We demonstrate a similar result for the cases of functional and structural motif-fingerprints without node roles, and global subgraph counts that form the basis of standard motif analysis. We also explicitly highlight that motif-role fingerprints are elemental to several popular metrics for quantifying the subgraph structure of directed complex networks, including motif distributions, directed clustering coefficient, and transitivity. The relationships between each of these metrics and motif-role fingerprints also suggest new subtypes of directed clustering coefficients and transitivities. Our results have potential utility in analyzing directed synaptic networks constructed from neuronal connectome data, such as in terms of centrality. Other potential applications include anomaly detection in networks, identification of similar networks and identification of similar nodes within networks. Matlab code for calculating all stated metrics following calculation of functional motif-role fingerprints is provided as S1 Matlab File.     

Geographically Modified PageRank Algorithms: Identifying the Spatial Concentration of Human Movement in a Geospatial Network

A network approach, which simplifies geographic settings as a form of nodes and links, emphasizes the connectivity and relationships of spatial features. Topological networks of spatial features are used to explore geographical connectivity and structures. The PageRank algorithm, a network metric, is often used to help identify important locations where people or automobiles concentrate in the geographical literature. However, geographic considerations, including proximity and location attractiveness, are ignored in most network metrics. The objective of the present study is to propose two geographically modified PageRank algorithms—Distance-Decay PageRank (DDPR) and Geographical PageRank (GPR)—that incorporate geographic considerations into PageRank algorithms to identify the spatial concentration of human movement in a geospatial network. Our findings indicate that in both intercity and within-city settings the proposed algorithms more effectively capture the spatial locations where people reside than traditional commonly-used network metrics. In comparing location attractiveness and distance decay, we conclude that the concentration of human movement is largely determined by the distance decay. This implies that geographic proximity remains a key factor in human mobility.     

Impact of Repeated Exposures on Information Spreading in Social Networks

Clustered structure of social networks provides the chances of repeated exposures to carriers with similar information. It is commonly believed that the impact of repeated exposures on the spreading of information is nontrivial. Does this effect increase the probability that an individual forwards a message in social networks? If so, to what extent does this effect influence people’s decisions on whether or not to spread information? Based on a large-scale microblogging data set, which logs the message spreading processes and users’ forwarding activities, we conduct a data-driven analysis to explore the answer to the above questions. The results show that an overwhelming majority of message samples are more probable to be forwarded under repeated exposures, compared to those under only a single exposure. For those message samples that cover various topics, we observe a relatively fixed, topic-independent multiplier of the willingness of spreading when repeated exposures occur, regardless of the differences in network structure. We believe that this finding reflects average people’s intrinsic psychological gain under repeated stimuli. Hence, it makes sense that the gain is associated with personal response behavior, rather than network structure. Moreover, we find that the gain is robust against the change of message popularity. This finding supports that there exists a relatively fixed gain brought by repeated exposures. Based on the above findings, we propose a parsimonious model to predict the saturated numbers of forwarding activities of messages. Our work could contribute to better understandings of behavioral psychology and social media analytics.     

Generative models of rich clubs in Hebbian neuronal networks and large-scale human brain networks

Rich clubs arise when nodes that are ‘rich’ in connections also form an elite, densely connected ‘club’. In brain networks, rich clubs incur high physical connection costs but also appear to be especially valuable to brain function. However, little is known about the selection pressures that drive their formation. Here, we take two complementary approaches to this question: firstly we show, using generative modelling, that the emergence of rich clubs in large-scale human brain networks can be driven by an economic trade-off between connection costs and a second, competing topological term. Secondly we show, using simulated neural networks, that Hebbian learning rules also drive the emergence of rich clubs at the microscopic level, and that the prominence of these features increases with learning time. These results suggest that Hebbian learning may provide a neuronal mechanism for the selection of complex features such as rich clubs. The neural networks that we investigate are explicitly Hebbian, and we argue that the topological term in our model of large-scale brain connectivity may represent an analogous connection rule. This putative link between learning and rich clubs is also consistent with predictions that integrative aspects of brain network organization are especially important for adaptive behaviour.     

Functional Brain Networks Develop from a “Local to Distributed” Organization

The mature human brain is organized into a collection of specialized functional networks that flexibly interact to support various cognitive functions. Studies of development often attempt to identify the organizing principles that guide the maturation of these functional networks. In this report, we combine resting state functional connectivity MRI (rs-fcMRI), graph analysis, community detection, and spring-embedding visualization techniques to analyze four separate networks defined in earlier studies. As we have previously reported, we find, across development, a trend toward ‘segregation’ (a general decrease in correlation strength) between regions close in anatomical space and ‘integration’ (an increased correlation strength) between selected regions distant in space. The generalization of these earlier trends across multiple networks suggests that this is a general developmental principle for changes in functional connectivity that would extend to large-scale graph theoretic analyses of large-scale brain networks. Communities in children are predominantly arranged by anatomical proximity, while communities in adults predominantly reflect functional relationships, as defined from adult fMRI studies. In sum, over development, the organization of multiple functional networks shifts from a local anatomical emphasis in children to a more “distributed” architecture in young adults. We argue that this “local to distributed” developmental characterization has important implications for understanding the development of neural systems underlying cognition. Further, graph metrics (e.g., clustering coefficients and average path lengths) are similar in child and adult graphs, with both showing “small-world”-like properties, while community detection by modularity optimization reveals stable communities within the graphs that are clearly different between young children and young adults. These observations suggest that early school age children and adults both have relatively efficient systems that may solve similar information processing problems in divergent ways.     

Functional Brain Networks Develop from a “Local to Distributed” Organization

The mature human brain is organized into a collection of specialized functional networks that flexibly interact to support various cognitive functions. Studies of development often attempt to identify the organizing principles that guide the maturation of these functional networks. In this report, we combine resting state functional connectivity MRI (rs-fcMRI), graph analysis, community detection, and spring-embedding visualization techniques to analyze four separate networks defined in earlier studies. As we have previously reported, we find, across development, a trend toward ‘segregation’ (a general decrease in correlation strength) between regions close in anatomical space and ‘integration’ (an increased correlation strength) between selected regions distant in space. The generalization of these earlier trends across multiple networks suggests that this is a general developmental principle for changes in functional connectivity that would extend to large-scale graph theoretic analyses of large-scale brain networks. Communities in children are predominantly arranged by anatomical proximity, while communities in adults predominantly reflect functional relationships, as defined from adult fMRI studies. In sum, over development, the organization of multiple functional networks shifts from a local anatomical emphasis in children to a more “distributed” architecture in young adults. We argue that this “local to distributed” developmental characterization has important implications for understanding the development of neural systems underlying cognition. Further, graph metrics (e.g., clustering coefficients and average path lengths) are similar in child and adult graphs, with both showing “small-world”-like properties, while community detection by modularity optimization reveals stable communities within the graphs that are clearly different between young children and young adults. These observations suggest that early school age children and adults both have relatively efficient systems that may solve similar information processing problems in divergent ways.     

Place-Based Attributes Predict Community Membership in a Mobile Phone Communication Network

Social networks can be organized into communities of closely connected nodes, a property known as modularity. Because diseases, information, and behaviors spread faster within communities than between communities, understanding modularity has broad implications for public policy, epidemiology and the social sciences. Explanations for community formation in social networks often incorporate the attributes of individual people, such as gender, ethnicity or shared activities. High modularity is also a property of large-scale social networks, where each node represents a population of individuals at a location, such as call flow between mobile phone towers. However, whether or not place-based attributes, including land cover and economic activity, can predict community membership for network nodes in large-scale networks remains unknown. We describe the pattern of modularity in a mobile phone communication network in the Dominican Republic, and use a linear discriminant analysis (LDA) to determine whether geographic context can explain community membership. Our results demonstrate that place-based attributes, including sugar cane production, urbanization, distance to the nearest airport, and wealth, correctly predicted community membership for over 70% of mobile phone towers. We observed a strongly positive correlation (r = 0.97) between the modularity score and the predictive ability of the LDA, suggesting that place-based attributes can accurately represent the processes driving modularity. In the absence of social network data, the methods we present can be used to predict community membership over large scales using solely place-based attributes.     

Experimental and Computational Analysis of a Large Protein Network That Controls Fat Storage Reveals the Design Principles of a Signaling Network

An approach combining genetic, proteomic, computational, and physiological analysis was used to define a protein network that regulates fat storage in budding yeast (Saccharomyces cerevisiae). A computational analysis of this network shows that it is not scale-free, and is best approximated by the Watts-Strogatz model, which generates “small-world” networks with high clustering and short path lengths. The network is also modular, containing energy level sensing proteins that connect to four output processes: autophagy, fatty acid synthesis, mRNA processing, and MAP kinase signaling. The importance of each protein to network function is dependent on its Katz centrality score, which is related both to the protein’s position within a module and to the module’s relationship to the network as a whole. The network is also divisible into subnetworks that span modular boundaries and regulate different aspects of fat metabolism. We used a combination of genetics and pharmacology to simultaneously block output from multiple network nodes. The phenotypic results of this blockage define patterns of communication among distant network nodes, and these patterns are consistent with the Watts-Strogatz model.