Concentric characterization and classification of complex network nodes: Application to an institutional collaboration network

Differently from theoretical scale-free networks, most real networks present multi-scale behavior, with nodes structured in different types of functional groups and communities. While the majority of approaches for classification of nodes in a complex network has relied on local measurements of the topology/connectivity around each node, valuable information about node functionality can be obtained by concentric (or hierarchical) measurements. This paper extends previous methodologies based on concentric measurements, by studying the possibility of using agglomerative clustering methods, in order to obtain a set of functional groups of nodes, considering particular institutional collaboration network nodes, including various known communities (departments of the University of Sao Paulo). Among the interesting obtained findings, we emphasize the scale-free nature of the network obtained, as well as identification of different patterns of authorship emerging from different areas (e.g. human and exact sciences). Another interesting result concerns the relatively uniform distribution of hubs along concentric levels, contrariwise to the non-uniform pattern found in theoretical scale-free networks such as the BA model. (C) 2008 Elsevier B.V. All rights reserved.

Hierarchical spatial organization of geographical networks

In this work, we propose a hierarchical extension of the polygonality index as the means to characterize geographical planar networks. By considering successive neighborhoods around each node, it is possible to obtain more complete information about the spatial order of the network at progressive spatial scales. The potential of the methodology is illustrated with respect to synthetic and real geographical networks.

On the effects of geographical constraints on task execution in complex

In the present work, the effects of spatial constraints on the efficiency of task execution in systems underlain by geographical complex networks are investigated, where the probability of connection decreases with the distance between the nodes. The investigation considers several configurations of the parameters defining the network connectivity, and the Barabasi-Albert network model is also considered for comparisons. The results show that the effect of connectivity is significant only for shorter tasks, the locality of connection simplied by the spatial constraints reduces efficiency, and the addition of edges can improve the efficiency of the execution, although with increasing locality of the connections the improvement is small.

EFFECTIVE NETWORKS FOR REAL-TIME DISTRIBUTED PROCESSING

This paper applies the concepts and methods of complex networks to the development of models and simulations of master-slave distributed real-time systems by introducing an upper bound in the allowable delivery time of the packets with computation results. Two representative interconnection models are taken into account: Uniformly random and scale free (Barabasi-Albert), including the presence of background traffic of packets. The obtained results include the identification of the uniformly random interconnectivity scheme as being largely more efficient than the scale-free counterpart. Also, increased latency tolerance of the application provides no help under congestion.

Multiple Pathways Analysis of Brain Functional Networks from EEG Signals: An Application to Real Data

In the present study, we propose a theoretical graph procedure to investigate multiple pathways in brain functional networks. By taking into account all the possible paths consisting of h links between the nodes pairs of the network, we measured the global network redundancy R (h) as the number of parallel paths and the global network permeability P (h) as the probability to get connected. We used this procedure to investigate the structural and dynamical changes in the cortical networks estimated from a dataset of high-resolution EEG signals in a group of spinal cord injured (SCI) patients during the attempt of foot movement. In the light of a statistical contrast with a healthy population, the permeability index P (h) of the SCI networks increased significantly (P < 0.01) in the Theta frequency band (3-6 Hz) for distances h ranging from 2 to 4. On the contrary, no significant differences were found between the two populations for the redundancy index R (h) . The most significant changes in the brain functional network of SCI patients occurred mainly in the lower spectral contents. These changes were related to an improved propagation of communication between the closest cortical areas rather than to a different level of redundancy. This evidence strengthens the hypothesis of the need for a higher functional interaction among the closest ROIs as a mechanism to compensate the lack of feedback from the peripheral nerves to the sensomotor areas.

Resilience of protein-protein interaction networks as determined by their large-scale topological features

The relationship between the structure and function of biological networks constitutes a fundamental issue in systems biology. Particularly, the structure of protein-protein interaction networks is related to important biological functions. In this work, we investigated how such a resilience is determined by the large scale features of the respective networks. Four species are taken into account, namely yeast Saccharomyces cerevisiae, worm Caenorhabditis elegans, fly Drosophila melanogaster and Homo sapiens. We adopted two entropy-related measurements (degree entropy and dynamic entropy) in order to quantify the overall degree of robustness of these networks. We verified that while they exhibit similar structural variations under random node removal, they differ significantly when subjected to intentional attacks (hub removal). As a matter of fact, more complex species tended to exhibit more robust networks. More specifically, we quantified how six important measurements of the networks topology (namely clustering coefficient, average degree of neighbors, average shortest path length, diameter, assortativity coefficient, and slope of the power law degree distribution) correlated with the two entropy measurements. Our results revealed that the fraction of hubs and the average neighbor degree contribute significantly for the resilience of networks. In addition, the topological analysis of the removed hubs indicated that the presence of alternative paths between the proteins connected to hubs tend to reinforce resilience. The performed analysis helps to understand how resilience is underlain in networks and can be applied to the development of protein network models.

To shut them up or to clarify: restraining the spread of rumors in online social networks

Restraining the spread of rumors in online social networks (OSNs) has long been an important but difficult problem to be addressed. Currently, there are mainly two types of methods 1) blocking rumors at the most influential users or community bridges, or 2) spreading truths to clarify the rumors. Each method claims the better performance among all the others according to their own considerations and environments. However, there must be one standing out of the rest. In this paper, we focus on this part of work. The difficulty is that there does not exist a universal standard to evaluate them. In order to address this problem, we carry out a series of empirical and theoretical analysis on the basis of the introduced mathematical model. Based on this mathematical platform, each method will be evaluated by using real OSN data.We have done three types of analysis in this work. First, we compare all the measures of locating important users. The results suggest that the degree and betweenness measures outperform all the others in the Facebook network. Second, we analyze the method of the truth clarification method, and find that this method has a long-term performance while the degree measure performs well only in the early stage. Third, in order to leverage these two methods, we further explore the strategy of different methods working together and their equivalence. Given a fixed budget in the real world, our analysis provides a potential solution to find out a better strategy by integrating both types of methods together. From both the academic and technical perspective, the work in this paper is an important step towards the most practical and optimal strategies of restraining rumors in OSNs.

Are the popular users always important for information dissemination in online social networks?

This article verifies the importance of popular users in OSNs. The results are counter-intuitive. First, for dissemination speed, a large amount of users can swiftly distribute information to the masses, but they are not highly-connected users. Second, for dissemination scale, many powerful forwarders in OSNs cannot be identified by the degree measure. Furthermore, to control dissemination, popular users cannot capture most bridges of social communities.

A sword with two edges: propagation studies on both positive and negative information in online social networks

Online social networks (OSN) have become one of the major platforms for people to exchange information. Both positive information (e.g., ideas, news and opinions) and negative information (e.g., rumors and gossips) spreading in social media can greatly influence our lives. Previously, researchers have proposed models to understand their propagation dynamics. However, those were merely simulations in nature and only focused on the spread of one type of information. Due to the human-related factors involved, simultaneous spread of negative and positive information cannot be thought of the superposition of two independent propagations. In order to fix these deficiencies, we propose an analytical model which is built stochastically from a node level up. It can present the temporal dynamics of spread such as the time people check newly arrived messages or forward them. Moreover, it is capable of capturing people's behavioral differences in preferring what to believe or disbelieve. We studied the social parameters impact on propagation using this model. We found that some factors such as people's preference and the injection time of the opposing information are critical to the propagation but some others such as the hearsay forwarding intention have little impact on it. The extensive simulations conducted on the real topologies confirm the high accuracy of our model.

Invasive Africanized honeybees change the structure of native pollination networks in Brazil

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Beta Diversity of Plant-Pollinator Networks and the Spatial Turnover of Pairwise Interactions

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Discriminating Different Classes of Biological Networks by Analyzing the Graphs Spectra Distribution

The brain's structural and functional systems, protein-protein interaction, and gene networks are examples of biological systems that share some features of complex networks, such as highly connected nodes, modularity, and small-world topology. Recent studies indicate that some pathologies present topological network alterations relative to norms seen in the general population. Therefore, methods to discriminate the processes that generate the different classes of networks (e. g., normal and disease) might be crucial for the diagnosis, prognosis, and treatment of the disease. It is known that several topological properties of a network (graph) can be described by the distribution of the spectrum of its adjacency matrix. Moreover, large networks generated by the same random process have the same spectrum distribution, allowing us to use it as a "fingerprint". Based on this relationship, we introduce and propose the entropy of a graph spectrum to measure the "uncertainty" of a random graph and the Kullback-Leibler and Jensen-Shannon divergences between graph spectra to compare networks. We also introduce general methods for model selection and network model parameter estimation, as well as a statistical procedure to test the nullity of divergence between two classes of complex networks. Finally, we demonstrate the usefulness of the proposed methods by applying them to (1) protein-protein interaction networks of different species and (2) on networks derived from children diagnosed with Attention Deficit Hyperactivity Disorder (ADHD) and typically developing children. We conclude that scale-free networks best describe all the protein-protein interactions. Also, we show that our proposed measures succeeded in the identification of topological changes in the network while other commonly used measures (number of edges, clustering coefficient, average path length) failed.

Disentangling social networks from spatiotemporal dynamics: the temporal structure of a dolphin society

Social networks are static illustrations of dynamic societies, within which social interactions are constantly changing. Fundamental sources of variation include ranging behaviour and temporal demographic changes. Spatiotemporal dynamics can favour or limit opportunities for individuals to interact, and then a network may not essentially represent social processes. We examined whether a social network can embed such nonsocial effects in its topology, whereby emerging modules depict spatially or temporally segregated individuals. To this end, we applied a combination of spatial, temporal and demographic analyses to a long-term study of the association patterns of Guiana dolphins, Sotalia guianensis. We found that association patterns are organized into a modular social network. Space use was unlikely to reflect these modules, since dolphins' ranging behaviour clearly overlapped. However, a temporal demographic turnover, caused by the exit/entrance of individuals (most likely emigration/immigration), defined three modules of associations occurring at different times. Although this factor could mask real social processes, we identified the temporal scale that allowed us to account for these demographic effects. By looking within this turnover period (32 months), we assessed fission-fusion dynamics of the poorly known social organization of Guiana dolphins. We highlight that spatiotemporal dynamics can strongly influence the structure of social networks. Our findings show that hypothetical social units can emerge due to the temporal opportunities for individuals to interact. Therefore, a thorough search for a satisfactory spatiotemporal scale that removes such nonsocial noise is critical when analysing a social system. (C) 2012 The Association for the Study of Animal Behaviour. Published by Elsevier Ltd. All rights reserved.

Complex network classification using partially self-avoiding deterministic walks

Complex networks have attracted increasing interest from various fields of science. It has been demonstrated that each complex network model presents specific topological structures which characterize its connectivity and dynamics. Complex network classification relies on the use of representative measurements that describe topological structures. Although there are a large number of measurements, most of them are correlated. To overcome this limitation, this paper presents a new measurement for complex network classification based on partially self-avoiding walks. We validate the measurement on a data set composed by 40000 complex networks of four well-known models. Our results indicate that the proposed measurement improves correct classification of networks compared to the traditional ones. (C) 2012 American Institute of Physics. [http://dx.doi.org/10.1063/1.4737515]

The structure and resilience of financial market networks

Financial markets can be viewed as a highly complex evolving system that is very sensitive to economic instabilities. The complex organization of the market can be represented in a suitable fashion in terms of complex networks, which can be constructed from stock prices such that each pair of stocks is connected by a weighted edge that encodes the distance between them. In this work, we propose an approach to analyze the topological and dynamic evolution of financial networks based on the stock correlation matrices. An entropy-related measurement is adopted to quantify the robustness of the evolving financial market organization. It is verified that the network topological organization suffers strong variation during financial instabilities and the networks in such periods become less robust. A statistical robust regression model is proposed to quantity the relationship between the network structure and resilience. The obtained coefficients of such model indicate that the average shortest path length is the measurement most related to network resilience coefficient. This result indicates that a collective behavior is observed between stocks during financial crisis. More specifically, stocks tend to synchronize their price evolution, leading to a high correlation between pair of stock prices, which contributes to the increase in distance between them and, consequently, decrease the network resilience. (C) 2012 American Institute of Physics. [doi:10.1063/1.3683467]