BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Vincenzo Nicosia

Vincenzo Nicosia appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
physics.soc-phSocial and Information Networkscond-mat.stat-mechphysics.data-ancond-mat.dis-nnnlin.CDBiological PhysicsComputational Engineering, Finance, and ScienceNeurons and Cognitionnlin.AOPopulations and EvolutionApplicationsData Structures and AlgorithmsInformation Theorymath.COmath.ITmath.SPphysics.comp-phq-fin.GNq-fin.STquant-ph

Catalog footprint

What is connected

34works
21topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

34 published item(s)

preprint2022arXiv

Impact of urban structure on infectious disease spreading

The ongoing SARS-CoV-2 pandemic has been holding the world hostage for more than a year now. Mobility is key to viral spreading and its restriction is the main non-pharmaceutical interventions to fight the virus expansion. Previous works have shown a connection between the structural organization of cities and the movement patterns of their residents. This puts urban centers in the focus of epidemic surveillance and interventions. Here we show that the organization of urban flows has a tremendous impact on disease spreading and on the amenability of different mitigation strategies. By studying anonymous and aggregated intra-urban flows in a variety of cities in the United States and other countries, and a combination of empirical analysis and analytical methods, we demonstrate that the response of cities to epidemic spreading can be roughly classified in two major types according to the overall organization of those flows. Hierarchical cities, where flows are concentrated primarily between mobility hotspots, are particularly vulnerable to the rapid spread of epidemics. Nevertheless, mobility restrictions in such types of cities are very effective in mitigating the spread of a virus. Conversely, in sprawled cities which present many centers of activity, the spread of an epidemic is much slower, but the response to mobility restrictions is much weaker and less effective. Investing resources on early monitoring and prompt ad-hoc interventions in more vulnerable cities may prove helpful in containing and reducing the impact of future pandemics.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Measuring Equality and Hierarchical Mobility on Abstract Complex Networks

The centrality of a node within a network, however it is measured, is a vital proxy for the importance or influence of that node, and the differences in node centrality generate hierarchies and inequalities. If the network is evolving in time, the influence of each node changes in time as well, and the corresponding hierarchies are modified accordingly. However, there is still a lack of systematic study into the ways in which the centrality of a node evolves when a graph changes. In this paper we introduce a taxonomy of metrics of equality and hierarchical mobility in networks that evolve in time. We propose an indicator of equality based on the classical Gini Coefficient from economics, and we quantify the hierarchical mobility of nodes, that is, how and to what extent the centrality of a node and its neighbourhood change over time. These measures are applied to a corpus of thirty time evolving network data sets from different domains. We show that the proposed taxonomy measures can discriminate between networks from different fields. We also investigate correlations between different taxonomy measures, and demonstrate that some of them have consistently strong correlations (or anti-correlations) across the entire corpus. The mobility and equality measures developed here constitute a useful toolbox for investigating the nature of network evolution, and also for discriminating between different artificial models hypothesised to explain that evolution.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Optimising the mitigation of epidemic spreading through targeted adoption of contact tracing apps

The ongoing COVID-19 pandemic is the first epidemic in human history in which digital contact-tracing has been deployed at a global scale. Tracking and quarantining all the contacts of individuals who test positive to a virus can help slowing-down an epidemic, but the impact of contact-tracing is severely limited by the generally low adoption of contact-tracing apps in the population. We derive here an analytical expression for the effectiveness of contact-tracing app installation strategies in a SIR model on a given contact graph. We propose a decentralised heuristic to improve the effectiveness of contact tracing under fixed adoption rates, which targets a set of individuals to install contact-tracing apps, and can be easily implemented. Simulations on a large number of real-world contact networks confirm that this heuristic represents a feasible alternative to the current state of the art.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Algorithmic complexity of multiplex networks

Multilayer networks preserve full information about the different interactions among the constituents of a complex system, and have recently proven quite useful in modelling transportation networks, social circles, and the human brain. A fundamental and still open problem is to assess if and when the multilayer representation of a system provides a qualitatively better model than the classical single-layer aggregated network. Here we tackle this problem from an algorithmic information theory perspective. We propose an intuitive way to encode a multilayer network into a bit string, and we define the complexity of a multilayer network as the ratio of the Kolmogorov complexity of the bit strings associated to the multilayer and to the corresponding aggregated graph. We find that there exists a maximum amount of additional information that a multilayer model can encode with respect to the equivalent single-layer graph. We show how our complexity measure can be used to obtain low-dimensional representations of multidimensional systems, to cluster multilayer networks into a small set of meaningful super-families, and to detect tipping points in the evolution of different time-varying multilayer graphs. Interestingly, the low-dimensional multiplex networks obtained with the proposed method also retain most of the dynamical properties of the original systems, as demonstrated for instance by the preservation of the epidemic threshold in the multiplex SIS model. These results suggest that information-theoretic approaches can be effectively employed for a more systematic analysis of static and time-varying multidimensional complex systems.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Disproportionate incidence of COVID-19 in African Americans correlates with dynamic segregation

Socio-economic disparities quite often have a central role in the unfolding of large-scale catastrophic events. One of the most concerning aspects of the ongoing COVID-19 pandemics is that it disproportionately affects people from Black and African American backgrounds creating an unexpected infection gap. Interestingly, the abnormal impact on these ethnic groups seem to be almost uncorrelated with other risk factors, including co-morbidity, poverty, level of education, access to healthcare, residential segregation, and response to cures. A proposed explanation for the observed incidence gap is that people from African American backgrounds are more often employed in low-income service jobs, and are thus more exposed to infection through face-to-face contacts, but the lack of direct data has not allowed to draw strong conclusions in this sense so far. Here we introduce the concept of dynamic segregation, that is the extent to which a given group of people is internally clustered or exposed to other groups, as a result of mobility and commuting habits. By analysing census and mobility data on more than 120 major US cities, we found that the dynamic segregation of African American communities is significantly associated with the weekly excess COVID-19 incidence and mortality in those communities. The results confirm that knowing where people commute to, rather than where they live, is much more relevant for disease modelling.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Optimal percolation in correlated multilayer networks with overlap

Multilayer networks have been found to be prone to abrupt cascading failures under random and targeted attacks, but most of the targeting algorithms proposed so far have been mainly tested on uncorrelated systems. Here we show that the size of the critical percolation set of a multilayer network is substantially affected by the presence of inter-layer degree correlations and edge overlap. We provide extensive numerical evidence which confirms that the state-of-the-art optimal percolation strategies consistently fail to identify minimal percolation sets in synthetic and real-world correlated multilayer networks, thus overestimating their robustness. We propose two new targeting algorithms, based on the local estimation of path disruptions away from a given node, and a family of Pareto-efficient strategies that take into account both intra-layer and inter-layer heuristics, and can be easily extended to multiplex networks with an arbitrary number of layers. We show that these strategies consistently outperform existing attacking algorithms, on both synthetic and real-world multiplex networks, and provide some interesting insights about the interplay of correlations and overlap in determining the hyperfragility of real-world multilayer networks. Overall, the results presented in the paper suggest that we are still far from having fully identified the salient ingredients determining the robustness of multiplex networks to targeted attacks.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Efficient On-line Computation of Visibility Graphs

A visibility algorithm maps time series into complex networks following a simple criterion. The resulting visibility graph has recently proven to be a powerful tool for time series analysis. However its straightforward computation is time-consuming and rigid, motivating the development of more efficient algorithms. Here we present a highly efficient method to compute visibility graphs with the further benefit of flexibility: on-line computation. We propose an encoder/decoder approach, with an on-line adjustable binary search tree codec for time series as well as its corresponding decoder for visibility graphs. The empirical evidence suggests the proposed method for computation of visibility graphs offers an on-line computation solution at no additional computation time cost. The source code is available online.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

On the spectral properties of Feigenbaum graphs

A Horizontal Visibility Graph (HVG) is a simple graph extracted from an ordered sequence of real values, and this mapping has been used to provide a combinatorial encryption of time series for the task of performing network based time series analysis. While some properties of the spectrum of these graphs --such as the largest eigenvalue of the adjacency matrix-- have been routinely used as measures to characterise time series complexity, a theoretic understanding of such properties is lacking. In this work we explore some algebraic and spectral properties of these graphs associated to periodic and chaotic time series. We focus on the family of Feigenbaum graphs, which are HVGs constructed in correspondence with the trajectories of one-parameter unimodal maps undergoing a period-doubling route to chaos (Feigenbaum scenario). For the set of values of the map's parameter $μ$ for which the orbits are periodic with period $2^n$, Feigenbaum graphs are fully characterised by two integers (n,k) and admit an algebraic structure. We explore the spectral properties of these graphs for finite n and k, and among other interesting patterns we find a scaling relation for the maximal eigenvalue and we prove some bounds explaining it. We also provide numerical and rigorous results on a few other properties including the determinant or the number of spanning trees. In a second step, we explore the set of Feigenbaum graphs obtained for the range of values of the map's parameter $μ$ for which the system displays chaos. We show that in this case, Feigenbaum graphs form an ensemble for each value of $μ$ and the system is typically weakly self-averaging. Unexpectedly, we find that while the largest eigenvalue can distinguish chaos from an iid process, it is not a good measure to quantify the chaoticity of the process, and that the eigenvalue density does a better job.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Efficient exploration of multiplex networks

Efficient techniques to navigate networks with local information are fundamental to sample large-scale online social systems and to retrieve resources in peer-to-peer systems. Biased random walks, i.e. walks whose motion is biased on properties of neighbouring nodes, have been largely exploited to design smart local strategies to explore a network, for instance by constructing maximally mixing trajectories or by allowing an almost uniform sampling of the nodes. Here we introduce and study biased random walks on multiplex networks, graphs where the nodes are related through different types of links organised in distinct and interacting layers, and we provide analytical solutions for their long-time properties, including the stationary occupation probability distribution and the entropy rate. We focus on degree-biased random walks and distinguish between two classes of walks, namely those whose transition probability depends on a number of parameters which is extensive in the number of layers, and those whose motion depends on intrinsically multiplex properties of the neighbouring nodes. We analyse the effect of the structure of the multiplex network on the steady-state behaviour of the walkers, and we find that heterogeneous degree distributions as well as the presence of inter-layer degree correlations and edge overlap determine the extent to which a multiplex can be efficiently explored by a biased walk. Finally we show that, in real-world multiplex transportation networks, the trade-off between efficient navigation and resilience to link failure has resulted into systems whose diffusion properties are qualitatively different from those of appropriately randomised multiplex graphs. This fact suggests that multiplexity is an important ingredient to include in the modelling of real-world systems.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Emergence of multiplex communities in collaboration networks

Community structures in collaboration networks reflect the natural tendency of individuals to organize their work in groups in order to better achieve common goals. In most of the cases, individuals exploit their connections to introduce themselves to new areas of interests, giving rise to multifaceted collaborations which span different fields. In this paper, we analyse collaborations in science and among movie actors as multiplex networks, where the layers represent respectively research topics and movie genres, and we show that communities indeed coexist and overlap at the different layers of such systems. We then propose a model to grow multiplex networks based on two mechanisms of intra and inter-layer triadic closure which mimic the real processes by which collaborations evolve. We show that our model is able to explain the multiplex community structure observed empirically, and we infer the strength of the two underlying social mechanisms from real-world systems. Being also able to correctly reproduce the values of intra-layer and inter-layer assortativity correlations, the model contributes to a better understanding of the principles driving the evolution of social networks.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Spatio-temporal analysis of micro economic activities in Rome reveals patterns of mixed-use urban evolution

Understanding urban growth is one with understanding how society evolves to satisfy the needs of its individuals in sharing a common space and adapting to the territory. We propose here a quantitative analysis of the historical development of a large urban area by investigating the spatial distribution and the age of commercial activities in the whole city of Rome. We find that the age of activities of various categories presents a very interesting double exponential trend, with a transition possibly related to the long-term economical effects determined by the oil crisis of the Seventies. The diversification of commercial categories, studied through various measures of entropy, shows, among other interesting features, a saturating behaviour with the density of activities. Moreover, different couples of commercial categories exhibit over the years a tendency to attract in space. Our results demonstrate that the spatio-temporal distribution of commercial activities can provide important insights on the urbanisation processes at work, revealing specific and not trivial socio-economical dynamics, as the presence of crisis periods and expansion trends, and contributing to the characterisation of the maturity of urban areas.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The multiplex dependency structure of financial markets

We propose here a multiplex network approach to investigate simultaneously different types of dependency in complex data sets. In particular, we consider multiplex networks made of four layers corresponding respectively to linear, non-linear, tail, and partial correlations among a set of financial time series. We construct the sparse graph on each layer using a standard network filtering procedure, and we then analyse the structural properties of the obtained multiplex networks. The study of the time evolution of the multiplex constructed from financial data uncovers important changes in intrinsically multiplex properties of the network, and such changes are associated with periods of financial stress. We observe that some features are unique to the multiplex structure and would not be visible otherwise by the separate analysis of the single-layer networks corresponding to each dependency measure.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Irreducibility of multilayer network dynamics: the case of the voter model

We address the issue of the reducibility of the dynamics on a multilayer network to an equivalent process on an aggregated single-layer network. As a typical example of models for opinion formation in social networks, we implement the voter model on a two-layer multiplex network, and we study its dynamics as a function of two control parameters, namely the fraction of edges simultaneously existing in both layers of the network (edge overlap), and the fraction of nodes participating in both layers (interlayer connectivity or degree of multiplexity). We compute the asymptotic value of the number of active links (interface density) in the thermodynamic limit, and the time to reach an absorbing state for finite systems, and we compare the numerical results with the analytical predictions on equivalent single-layer networks obtained through various possible aggregation procedures. We find a large region of parameters where the interface density of large multiplexes gives systematic deviations from that of the aggregates. We show that neither of the standard aggregation procedures is able to capture the highly nonlinear increase in the lifetime of a finite size multiplex at small interlayer connectivity. These results indicate that multiplexity should be appropriately taken into account when studying voter model dynamics, and that, in general, single-layer approximations might be not accurate enough to properly understand processes occurring on multiplex networks, since they might flatten out relevant dynamical details.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Measuring and modelling correlations in multiplex networks

The interactions among the elementary components of many complex systems can be qualitatively different. Such systems are therefore naturally described in terms of multiplex or multi-layer networks, i.e. networks where each layer stands for a different type of interaction between the same set of nodes. There is today a growing interest in understanding when and why a description in terms of a multiplex network is necessary and more informative than a single-layer projection. Here, we contribute to this debate by presenting a comprehensive study of correlations in multiplex networks. Correlations in node properties, especially degree-degree correlations, have been thoroughly studied in single-layer networks. Here we extend this idea to investigate and characterize correlations between the different layers of a multiplex network. Such correlations are intrinsically multiplex, and we first study them empirically by constructing and analyzing several multiplex networks from the real-world. In particular, we introduce various measures to characterize correlations in the activity of the nodes and in their degree at the different layers, and between activities and degrees. We show that real-world networks exhibit indeed non-trivial multiplex correlations. For instance, we find cases where two layers of the same multiplex network are positively correlated in terms of node degrees, while other two layers are negatively correlated. We then focus on constructing synthetic multiplex networks, proposing a series of models to reproduce the correlations observed empirically and/or to assess their relevance.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Network structure of multivariate time series

Our understanding of a variety of phenomena in physics, biology and economics crucially depends on the analysis of multivariate time series. While a wide range of tools and techniques for time series analysis already exist, the increasing availability of massive data structures calls for new approaches for multidimensional signal processing. We present here a non-parametric method to analyse multivariate time series, based on the mapping of a multidimensional time series into a multilayer network, which allows to extract information on a high dimensional dynamical system through the analysis of the structure of the associated multiplex network. The method is simple to implement, general, scalable, does not require ad hoc phase space partitioning, and is thus suitable for the analysis of large, heterogeneous and non-stationary time series. We show that simple structural descriptors of the associated multiplex networks allow to extract and quantify nontrivial properties of coupled chaotic maps, including the transition between different dynamical phases and the onset of various types of synchronization. As a concrete example we then study financial time series, showing that a multiplex network analysis can efficiently discriminate crises from periods of financial stability, where standard methods based on time-series symbolization often fail.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Characteristic exponents of complex networks

We present a novel way to characterize the structure of complex networks by studying the statistical properties of the trajectories of random walks over them. We consider time series corresponding to different properties of the nodes visited by the walkers. We show that the analysis of the fluctuations of these time series allows to define a set of characteristic exponents which capture the local and global organization of a network. This approach provides a way of solving two classical problems in network science, namely the systematic classification of networks, and the identification of the salient properties of growing networks. The results contribute to the construction of a unifying framework for the investigation of the structure and dynamics of complex systems.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Evolutionary dynamics of time-resolved social interactions

Cooperation among unrelated individuals is frequently observed in social groups when their members combine efforts and resources to obtain a shared benefit that is unachievable by an individual alone. However, understanding why cooperation arises despite the natural tendency of individuals towards selfish behavior is still an open problem and represents one of the most fascinating challenges in evolutionary dynamics. Recently, the structural characterization of the networks in which social interactions take place has shed some light on the mechanisms by which cooperative behavior emerges and eventually overcomes the natural temptation to defect. In particular, it has been found that the heterogeneity in the number of social ties and the presence of tightly knit communities lead to a significant increase in cooperation as compared with the unstructured and homogeneous connection patterns considered in classical evolutionary dynamics. Here, we investigate the role of social-ties dynamics for the emergence of cooperation in a family of social dilemmas. Social interactions are in fact intrinsically dynamic, fluctuating, and intermittent over time, and they can be represented by time-varying networks. By considering two experimental data sets of human interactions with detailed time information, we show that the temporal dynamics of social ties has a dramatic impact on the evolution of cooperation: the dynamics of pairwise interactions favors selfish behavior.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Geo-Spotting: Mining Online Location-based Services for Optimal Retail Store Placement

The problem of identifying the optimal location for a new retail store has been the focus of past research, especially in the field of land economy, due to its importance in the success of a business. Traditional approaches to the problem have factored in demographics, revenue and aggregated human flow statistics from nearby or remote areas. However, the acquisition of relevant data is usually expensive. With the growth of location-based social networks, fine grained data describing user mobility and popularity of places has recently become attainable. In this paper we study the predictive power of various machine learning features on the popularity of retail stores in the city through the use of a dataset collected from Foursquare in New York. The features we mine are based on two general signals: geographic, where features are formulated according to the types and density of nearby places, and user mobility, which includes transitions between venues or the incoming flow of mobile users from distant areas. Our evaluation suggests that the best performing features are common across the three different commercial chains considered in the analysis, although variations may exist too, as explained by heterogeneities in the way retail facilities attract users. We also show that performance improves significantly when combining multiple features in supervised learning algorithms, suggesting that the retail success of a business may depend on multiple factors.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Non-linear growth and condensation in multiplex networks

Different types of interactions coexist and coevolve to shape the structure and function of a multiplex network. We propose here a general class of growth models in which the various layers of a multiplex network coevolve through a set of non-linear preferential attachment rules. We show, both numerically and analytically, that by tuning the level of non-linearity these models allow to reproduce either homogeneous or heterogeneous degree distributions, together with positive or negative degree correlations across layers. In particular, we derive the condition for the appearance of a condensed state in which one node in each layer attracts an extensive fraction of all the edges.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Structural measures for multiplex networks

Many real-world complex systems consist of a set of elementary units connected by relationships of different kinds. All such systems are better described in terms of multiplex networks, where the links at each layer represent a different type of interaction between the same set of nodes, rather than in terms of (single-layer) networks. In this paper we present a general framework to describe and study multiplex networks, whose links are either unweighted or weighted. In particular we propose a series of measures to characterize the multiplexicity of the systems in terms of: i) basic node and link properties such as the node degree, and the edge overlap and reinforcement, ii) local properties such as the clustering coefficient and the transitivity, iii) global properties related to the navigability of the multiplex across the different layers. The measures we introduce are validated on a genuine multiplex data set of Indonesian terrorists, where information among 78 individuals are recorded with respect to mutual trust, common operations, exchanged communications and business relationships.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Applications of Temporal Graph Metrics to Real-World Networks

Real world networks exhibit rich temporal information: friends are added and removed over time in online social networks; the seasons dictate the predator-prey relationship in food webs; and the propagation of a virus depends on the network of human contacts throughout the day. Recent studies have demonstrated that static network analysis is perhaps unsuitable in the study of real world network since static paths ignore time order, which, in turn, results in static shortest paths overestimating available links and underestimating their true corresponding lengths. Temporal extensions to centrality and efficiency metrics based on temporal shortest paths have also been proposed. Firstly, we analyse the roles of key individuals of a corporate network ranked according to temporal centrality within the context of a bankruptcy scandal; secondly, we present how such temporal metrics can be used to study the robustness of temporal networks in presence of random errors and intelligent attacks; thirdly, we study containment schemes for mobile phone malware which can spread via short range radio, similar to biological viruses; finally, we study how the temporal network structure of human interactions can be exploited to effectively immunise human populations. Through these applications we demonstrate that temporal metrics provide a more accurate and effective analysis of real-world networks compared to their static counterparts.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Characteristic times of biased random walks on complex networks

We consider degree-biased random walkers whose probability to move from a node to one of its neighbors of degree $k$ is proportional to $k^α$, where $α$ is a tuning parameter. We study both numerically and analytically three types of characteristic times, namely: i) the time the walker needs to come back to the starting node, ii) the time it takes to visit a given node for the first time, and iii) the time it takes to visit all the nodes of the network. We consider a large data set of real-world networks and we show that the value of $α$ which minimizes the three characteristic times is different from the value $α_{\rm min}=-1$ analytically found for uncorrelated networks in the mean-field approximation. In addition to this, we found that assortative networks have preferentially a value of $α_{\rm min}$ in the range $[-1,-0.5]$, while disassortative networks have $α_{\rm min}$ in the range $[-0.5, 0]$. We derive an analytical relation between the degree correlation exponent $ν$ and the optimal bias value $α_{\rm min}$, which works well for real-world assortative networks. When only local information is available, degree-biased random walks can guarantee smaller characteristic times than the classical unbiased random walks, by means of an appropriate tuning of the motion bias.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Co-evolution of networks and quantum dynamics: a generalization of preferential attachment

We propose a model of network growth in which the network is co-evolving together with the dynamics of a quantum mechanical system, namely a quantum walk taking place over the network. The model naturally generalizes the Barabási-Albert model of preferential attachment and has a rich set of tunable parameters, such as the initial conditions of the dynamics or the interaction of the system with its environment. We show that the model produces networks with two-modal power-law degree distributions, super-hubs, finite clustering coefficient, small-world behaviour and non-trivial degree-degree correlations.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Graph Metrics for Temporal Networks

Temporal networks, i.e., networks in which the interactions among a set of elementary units change over time, can be modelled in terms of time-varying graphs, which are time-ordered sequences of graphs over a set of nodes. In such graphs, the concepts of node adjacency and reachability crucially depend on the exact temporal ordering of the links. Consequently, all the concepts and metrics proposed and used for the characterisation of static complex networks have to be redefined or appropriately extended to time-varying graphs, in order to take into account the effects of time ordering on causality. In this chapter we discuss how to represent temporal networks and we review the definitions of walks, paths, connectedness and connected components valid for graphs in which the links fluctuate over time. We then focus on temporal node-node distance, and we discuss how to characterise link persistence and the temporal small-world behaviour in this class of networks. Finally, we discuss the extension of classic centrality measures, including closeness, betweenness and spectral centrality, to the case of time-varying graphs, and we review the work on temporal motifs analysis and the definition of modularity for temporal graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Growing multiplex networks

We propose a modeling framework for growing multiplexes where a node can belong to different networks. We define new measures for multiplexes and we identify a number of relevant ingredients for modeling their evolution such as the coupling between the different layers and the arrival time distribution of nodes. The topology of the multiplex changes significantly in the different cases under consideration, with effects of the arrival time of nodes on the degree distribution, average shortest paths and interdependence.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Motion-induced synchronization in metapopulations of mobile agents

We study the influence of motion on the emergence of synchronization in a metapopulation of random walkers moving on a heterogeneous network and subject to Kuramoto interactions at the network nodes. We discover a novel mechanism of transition to macroscopic dynamical order induced by the walkers' motion. Furthermore, we observe two different microscopic paths to synchronization: depending on the rules of the motion, either low-degree nodes or the hubs drive the whole system towards synchronization. We provide analytical arguments to understand these results.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Non-parametric resampling of random walks for spectral network clustering

Parametric resampling schemes have been recently introduced in complex network analysis with the aim of assessing the statistical significance of graph clustering and the robustness of community partitions. We propose here a method to replicate structural features of complex networks based on the non-parametric resampling of the transition matrix associated with an unbiased random walk on the graph. We test this bootstrapping technique on synthetic and real-world modular networks and we show that the ensemble of replicates obtained through resampling can be used to improve the performance of standard spectral algorithms for community detection.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Phase transition in the economically modeled growth of a cellular nervous system

Spatially-embedded complex networks, such as nervous systems, the Internet and transportation networks, generally have non-trivial topological patterns of connections combined with nearly minimal wiring costs. However the growth rules shaping these economical trade-offs between cost and topology are not well understood. Here we study the cellular nervous system of the nematode worm C. elegans, together with information on the birth times of neurons and on their spatial locations. We find that the growth of this network undergoes a transition from an accelerated to a constant increase in the number of links (synaptic connections) as a function of the number of nodes (neurons). The time of this phase transition coincides closely with the observed moment of hatching, when development switches metamorphically from oval to larval stages. We use graph analysis and generative modelling to show that the transition between different growth regimes, as well as its coincidence with the moment of hatching, can be explained by a dynamic economical model which incorporates a trade-off between topology and cost that is continuously negotiated and re-negotiated over developmental time. As the body of the animal progressively elongates, the cost of longer distance connections is increasingly penalised. This growth process regenerates many aspects of the adult nervous system's organization, including the neuronal membership of anatomically pre-defined ganglia. We expect that similar economical principles can be found in the development of other biological or man-made spatially-embedded complex systems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Remote synchronization reveals network symmetries and functional modules

We study a Kuramoto model in which the oscillators are associated with the nodes of a complex network and the interactions include a phase frustration, thus preventing full synchronization. The system organizes into a regime of remote synchronization where pairs of nodes with the same network symmetry are fully synchronized, despite their distance on the graph. We provide analytical arguments to explain this result and we show how the frustration parameter affects the distribution of phases. An application to brain networks suggests that anatomical symmetry plays a role in neural synchronization by determining correlated functional modules across distant locations.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Social and place-focused communities in location-based online social networks

Thanks to widely available, cheap Internet access and the ubiquity of smartphones, millions of people around the world now use online location-based social networking services. Understanding the structural properties of these systems and their dependence upon users' habits and mobility has many potential applications, including resource recommendation and link prediction. Here, we construct and characterise social and place-focused graphs by using longitudinal information about declared social relationships and about users' visits to physical places collected from a popular online location-based social service. We show that although the social and place-focused graphs are constructed from the same data set, they have quite different structural properties. We find that the social and location-focused graphs have different global and meso-scale structure, and in particular that social and place-focused communities have negligible overlap. Consequently, group inference based on community detection performed on the social graph alone fails to isolate place-focused groups, even though these do exist in the network. By studying the evolution of tie structure within communities, we show that the time period over which location data are aggregated has a substantial impact on the stability of place-focused communities, and that information about place-based groups may be more useful for user-centric applications than that obtained from the analysis of social communities alone.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Social cohesion, structural holes, and a tale of two measures

In the social sciences, the debate over the structural foundations of social capital has long vacillated between two positions on the relative benefits associated with two types of social structures: closed structures, rich in third-party relationships, and open structures, rich in structural holes and brokerage opportunities. In this paper, we engage with this debate by focusing on the measures typically used for formalising the two conceptions of social capital: clustering and effective size. We show that these two measures are simply two sides of the same coin, as they can be expressed one in terms of the other through a simple functional relation. Building on this relation, we then attempt to reconcile closed and open structures by proposing a new measure, Simmelian brokerage, that captures opportunities of brokerage between otherwise disconnected cohesive groups of contacts. Implications of our findings for research on social capital and complex networks are discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Elementary processes governing the evolution of road networks

Urbanisation is a fundamental phenomenon whose quantitative characterisation is still inadequate. We report here the empirical analysis of a unique data set regarding almost 200 years of evolution of the road network in a large area located north of Milan (Italy). We find that urbanisation is characterised by the homogenisation of cell shapes, and by the stability throughout time of high-centrality roads which constitute the backbone of the urban structure, confirming the importance of historical paths. We show quantitatively that the growth of the network is governed by two elementary processes: (i) `densification', corresponding to an increase in the local density of roads around existing urban centres and (ii) `exploration', whereby new roads trigger the spatial evolution of the urbanisation front. The empirical identification of such simple elementary mechanisms suggests the existence of general, simple properties of urbanisation and opens new directions for its modelling and quantitative description.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Controlling centrality in complex networks

Spectral centrality measures allow to identify influential individuals in social groups, to rank Web pages by their popularity, and even to determine the impact of scientific researches. The centrality score of a node within a network crucially depends on the entire pattern of connections, so that the usual approach is to compute the node centralities once the network structure is assigned. We face here with the inverse problem, that is, we study how to modify the centrality scores of the nodes by acting on the structure of a given network. We prove that there exist particular subsets of nodes, called controlling sets, which can assign any prescribed set of centrality values to all the nodes of a graph, by cooperatively tuning the weights of their out-going links. We show that many large networks from the real world have surprisingly small controlling sets, containing even less than 5-10% of the nodes. These results suggest that rankings obtained from spectral centrality measures have to be considered with extreme care, since they can be easily controlled and even manipulated by a small group of nodes acting in a coordinated way.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Maximal-entropy random walks in complex networks with limited information

Maximization of the entropy rate is an important issue to design diffusion processes aiming at a well-mixed state. We demonstrate that it is possible to construct maximal-entropy random walks with only local information on the graph structure. In particular, we show that an almost maximal-entropy random walk is obtained when the step probabilities are proportional to a power of the degree of the target node, with an exponent $α$ that depends on the degree-degree correlations, and is equal to 1 in uncorrelated graphs.

0 citations0 reviewsNo code linkedOpen access