Search

Message passing (MP) is a computational technique used to find approximate solutions to a variety of problems defined on networks. MP approximations are generally accurate in locally tree-like networks but require corrections to maintain their accuracy level in networks rich with short cycles. However, MP may already be computationally challenging on very large networks and additional costs incurred by correcting for cycles could be be prohibitive. We show how the issue can be addressed. By allowing each node in the network to have its own level of approximation, one can focus on improving the accuracy of MP approaches in a targeted manner. We perform a systematic analysis of 109 real-world networks and show that our node-based MP approximation is able to increase both the accuracy and speed of traditional MP approaches. We find that, compared to conventional message passing, a heterogeneous approach based on a simple heuristic is more accurate in 81% of tested networks, faster in 64% of cases, and both more accurate and faster in 49% of cases., Comment: 11 pages, 8 figures, 3 tables

Individuals involved in common group activities/settings -- e.g., college students that are enrolled in the same class and/or live in the same dorm -- are exposed to recurrent contacts of physical proximity. These contacts are known to mediate the spread of an infectious disease, however, it is not obvious how the properties of the spreading process are determined by the structure of and the interrelation among the group settings that are at the root of those recurrent interactions. Here, we show that reshaping the organization of groups within a population can be used as an effective strategy to decrease the severity of an epidemic. Specifically, we show that when group structures are sufficiently correlated -- e.g., the likelihood for two students living in the same dorm to attend the same class is sufficiently high -- outbreaks are longer but milder than for uncorrelated group structures. Also, we show that the effectiveness of interventions for disease containment increases as the correlation among group structures increases. We demonstrate the practical relevance of our findings by taking advantage of data about housing and attendance of students at the Indiana University campus in Bloomington. By appropriately optimizing the assignment of students to dorms based on their enrollment, we are able to observe a two- to five-fold reduction in the severity of simulated epidemic processes., Comment: 9 pages, 4 figures + Supplemental Material

Estimating the influence that individual nodes have on one another in a Boolean network is essential to predict and control the system's dynamical behavior, for example, detecting key therapeutic targets to control pathways in models of biological signaling and regulation. Exact estimation is generally not possible due to the fact that the number of configurations that must be considered grows exponentially with the system size. However, approximate, scalable methods exist in the literature. These methods can be divided in two main classes: (i) graph-theoretic methods that rely on representations of Boolean dynamics into static graphs, (ii) and mean-field approaches that describe average trajectories of the system but neglect dynamical correlations. Here, we compare systematically the performance of these state-of-the-art methods on a large collection of real-world gene regulatory networks. We find comparable performance across methods. All methods underestimate the ground truth, with mean-field approaches having a better recall but a worse precision than graph-theoretic methods. Computationally speaking, graph-theoretic methods are faster than mean-field ones in sparse networks, but are slower in dense networks. The preference of which method to use, therefore, depends on a network's connectivity and the relative importance of recall vs. precision for the specific application at hand., Comment: 11 pages, 5 figures + 7 supplementary figures

The use of quantitative metrics to gauge the impact of scholarly publications, authors, and disciplines is predicated on the availability of reliable annotation data. Citation and download counts are widely available from digital libraries. However, current annotation systems rely on proprietary labels, refer to journals or articles but not authors, and are manually curated. To address these limitations, we present a social framework based on crowdsourced annotations of scholars, designed to keep up with the rapidly evolving disciplinary and interdisciplinary landscape. The crowdsourcing approach has the added advantage that when combined with citation information about the authors, it enables the computation of discipline-specific statistics and discipline-neutral impact metrics. In turn, these impact metrics create an incentive for users to provide disciplinary annotations of authors.

L��vy flights represent the best strategy to randomly search for a target in an unknown environment, and have been widely observed in many animal species. Here, we inspect and discuss recent results concerning human behavior and cognition. Different studies have shown that human mobility can be described in terms of L��vy flights, while fresh evidence indicates that the same pattern accounts for human mental searches in online gambling sites. Thus, L��vy flights emerge as a unifying concept with broad cross-disciplinary implications. We argue that the ubiquity of such a pattern, both in behavior and cognition, suggests that the brain regions responsible for this behavior are likely to be evolutionarily old (i.e. no frontal cortex is involved), and that fMRI techniques might help to confirm this hypothesis.

Recent analysis of empirical data [F. Radicchi, A. Baronchelli & L.A.N. Amaral. PloS ONE 7, e029910 (2012)] showed that humans adopt L��vy flight strategies when exploring the bid space in on-line auctions. A game theoretical model proved that the observed L��vy exponents are nearly optimal, being close to the exponent value that guarantees the maximal economical return to players. Here, we rationalize these findings by adopting an evolutionary perspective. We show that a simple evolutionary process is able to account for the empirical measurements with the only assumption that the reproductive fitness of a player is proportional to her search ability. Contrarily to previous modeling, our approach describes the emergence of the observed exponent without resorting to any strong assumptions on the initial searching strategies. Our results generalize earlier research, and open novel questions in cognitive, behavioral and evolutionary sciences., 8 pages, 4 figures

Two methods for comparing impact factors and citation rates across fields of science are tested against each other using citations to the 3,705 journals in the Science Citation Index 2010 (CD-Rom version of SCI) and the 13 field categories used for the Science and Engineering Indicators of the US National Science Board. We compare (i) normalization by counting citations in proportion to the length of the reference list (1/N of references) with (ii) rescaling by dividing citation scores by the arithmetic mean of the citation rate of the cluster. Rescaling is analytical and therefore independent of the quality of the attribution to the sets, whereas fractional counting provides an empirical strategy for normalization among sets (by evaluating the between-group variance). By the fairness test of Radicchi & Castellano (2012a), rescaling outperforms fractional counting of citations for reasons that we consider., Journal of the American Society for Information Science and Technology (2013, in press)

Community structure is one of the main structural features of networks, revealing both their internal organization and the similarity of their elementary units. Despite the large variety of methods proposed to detect communities in graphs, there is a big need for multi-purpose techniques, able to handle different types of datasets and the subtleties of community structure. In this paper we present OSLOM (Order Statistics Local Optimization Method), the first method capable to detect clusters in networks accounting for edge directions, edge weights, overlapping communities, hierarchies and community dynamics. It is based on the local optimization of a fitness function expressing the statistical significance of clusters with respect to random fluctuations, which is estimated with tools of Extreme and Order Statistics. OSLOM can be used alone or as a refinement procedure of partitions/covers delivered by other techniques. We have also implemented sequential algorithms combining OSLOM with other fast techniques, so that the community structure of very large networks can be uncovered. Our method has a comparable performance as the best existing algorithms on artificial benchmark graphs. Several applications on real networks are shown as well. OSLOM is implemented in a freely available software (http://www.oslom.org), and we believe it will be a valuable tool in the analysis of networks., The project ICTeCollective acknowledges the financial support of the Future and Emerging Technologies (FET) programme within the Seventh Framework Programme for Research of the European Commission, under FET-Open grant number 238597. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.