Hybrid journal (It can contain Open Access articles) ISSN (Print) 2051-1310 - ISSN (Online) 2051-1329 Published by Oxford University Press[372 journals]

Authors:Jalili M; Perc M. Pages: 665 - 693 Abstract: Information cascades are important dynamical processes in complex networks. An information cascade can describe the spreading dynamics of rumour, disease, memes, or marketing campaigns, which initially start from a node or a set of nodes in the network. If conditions are right, information cascades rapidly encompass large parts of the network, thus leading to epidemics or epidemic spreading. Certain network topologies are particularly conducive to epidemics, while others decelerate and even prohibit rapid information spreading. Here we review models that describe information cascades in complex networks, with an emphasis on the role and consequences of node centrality. In particular, we present simulation results on sample networks that reveal just how relevant the centrality of initiator nodes is on the latter development of an information cascade, and we define the spreading influence of a node as the fraction of nodes that is activated as a result of the initial activation of that node. A systemic review of existing results shows that some centrality measures, such as the degree and betweenness, are positively correlated with the spreading influence, while other centrality measures, such as eccentricity and the information index, have negative correlation. A positive correlation implies that choosing a node with the highest centrality value will activate the largest number of nodes, while a negative correlation implies that the node with the lowest centrality value will have the same effect. We discuss possible applications of these results, and we emphasize how information cascades can help us identify nodes with the highest spreading capability in complex networks. PubDate: 2017-07-06 DOI: 10.1093/comnet/cnx019 Issue No:Vol. 5, No. 5 (2017)

Authors:Cinelli M; Ferraro G, Iovanella A. Pages: 694 - 711 Abstract: The dyadic effect is a phenomenon that occurs when the number of links between nodes sharing a common feature is larger than expected if the features are distributed randomly on the network. In this article, we consider the case when nodes are distinguished by a binary characteristic. Under these circumstances, two independent parameters, namely dyadicity and heterophilicity are able to detect the presence of the dyadic effect and to measure how much the considered characteristic affects the network topology. The distribution of nodes characteristics can be investigated within a two-dimensional space that represents the feasible region of the dyadic effect, which is bound by two upper bounds on dyadicity and heterophilicity. Using some network structural arguments, we are able to improve such upper bounds and introduce two new lower bounds, providing a reduction of the feasible region of the dyadic effect as well as constraining dyadicity and heterophilicity within a specific range. Some computational experiences show the bounds effectiveness and their usefulness with regards to different classes of networks. PubDate: 2017-03-22 DOI: 10.1093/comnet/cnx002 Issue No:Vol. 5, No. 5 (2017)

Authors:Zhang J; Moura JF, Zhang J. Pages: 712 - 733 Abstract: Propagation of contagion in networks depends on the graph topology. This article is concerned with studying the time-asymptotic behaviour of the extended contact processes on static, undirected, finite-size networks. This is a contact process with nonzero exogenous infection rate (also known as the $\epsilon$-susceptible-infected-susceptible model). The only known analytical characterization of the equilibrium distribution of this process is for complete networks. For large networks with arbitrary topology, it is infeasible to numerically solve for the equilibrium distribution since it requires solving the eigenvalue-eigenvector problem of a matrix that is exponential in $N$, the size of the network. We derive a condition on the infection rates under which, depending on the degree distribution of the network, the equilibrium distribution of extended contact processes on arbitrary, finite-size networks is well approximated by a closed-form formulation. We confirm the goodness of the approximation with small networks answering inference questions like the distribution of the percentage of infected individuals and the most-probable equilibrium configuration. We then use the approximation to analyse the equilibrium distribution of the extended contact process on the 4941-node US Western power grid. PubDate: 2017-05-15 DOI: 10.1093/comnet/cnx003 Issue No:Vol. 5, No. 5 (2017)

Authors:Chakraborty T. Pages: 734 - 749 Abstract: Real-world complex networks usually contain vertices with different structural and functional properties. Usually vertices with similar properties form dense substructures, often known as communities, in the network. Analysing such communities in large networks has rapidly become one of the major agenda in network science. A major limitation of most of the community finding algorithms is that they are highly dependent on the ordering in which vertices are processed, thus minimum permutation in vertex ordering might result in different community structures. Interestingly, despite such variability, there exist groups of vertices which are invariant and remain persistent over the time period. In this article, we propose for the first time a novel algorithm, DIGPerm to identify such invariant groups of vertices whose assignment to communities are, quite remarkably, not affected by any vertex ordering. DIGPerm is built on the notion of stability of a node in a community and aims at maximizing the stability of all the nodes using a multi-stage greedy framework in order to detect the invariant groups. We run our algorithm on both synthetic and real-world networks and test its efficiency by comparing it with consensus of other state-of-the-art community detection methods. We observe that, the detected groups, quite remarkably, represent the cores of the community structure in a network. Finally, we conduct an analysis on two dynamic networks to show that even if the community structure changes over time, the invariant groups merely change, resulting in more cohesive substructure of a network. PubDate: 2017-05-13 DOI: 10.1093/comnet/cnx004 Issue No:Vol. 5, No. 5 (2017)

Authors:Giscard P; Rochet P, Wilson RC. Pages: 750 - 775 Abstract: Signed networks have long been used to represent social relations of amity (+) and enmity ($-$) between individuals. Group of individuals who are cyclically connected are said to be balanced if the number of negative edges in the cycle is even and unbalanced otherwise. In its earliest and most natural formulation, the balance of a social network was thus defined from its simple cycles, cycles which do not visit any vertex more than once. Because of the inherent difficulty associated with finding such cycles on very large networks, social balance has since then been studied via other means. In this article, we present the balance as measured from the simple cycles and primitive orbits of social networks. We specifically provide two measures of balance: the proportion $R_\ell$ of negative simple cycles of length $\ell$ for each $\ell\leq 20$ which generalizes the triangle index, and a ratio $K_\ell$ which extends the relative signed clustering coefficient introduced by Kunegis. To do so, we use a Monte Carlo implementation of a novel exact formula for counting the simple cycles on any weighted directed graph. Our method is free from the double-counting problem affecting previous cycle-based approaches, does not require edge-reciprocity of the underlying network, provides a grey-scale measure of balance for each cycle length separately and is sufficiently tractable that it can be implemented on a standard desktop computer. We observe that social networks exhibit strong inter-edge correlations favouring balanced situations and we determine the corresponding correlation length $\xi$. For longer simple cycles, $R_\ell$ undergoes a sharp transition to values expected from an uncorrelated model. This transition is absent from synthetic random networks, strongly suggesting that it carries a sociological meaning warranting further research. PubDate: 2017-05-05 DOI: 10.1093/comnet/cnx005 Issue No:Vol. 5, No. 5 (2017)

Authors:Fish B; Kushwaha R, Turán G. Pages: 776 - 794 Abstract: Betweenness centrality of a vertex in a graph measures the fraction of shortest paths going through the vertex. This is a basic notion for determining the importance of a vertex in a network. The $k$-betweenness centrality of a vertex is defined similarly, but only considers shortest paths of length at most $k$. The sequence of $k$-betweenness centralities for all possible values of $k$ forms the betweenness centrality profile of a vertex. We study properties of betweenness centrality profiles in trees.We show that for scale-free random trees, for fixed $k$, the expectation of $k$-betweenness centrality strictly decreases as the index of the vertex increases. We also analyse worst-case properties of profiles in terms of the distance of profiles from being monotone, and the number of times pairs of profiles can cross. This is related to whether $k$-betweenness centrality, for small values of $k$, may be used instead of having to consider all shortest paths. Bounds are given that are optimal in order of magnitude. We also present some experimental results for scale-free random trees. PubDate: 2017-05-03 DOI: 10.1093/comnet/cnx007 Issue No:Vol. 5, No. 5 (2017)

Authors:Maliah S; Puzis R, Shani G. Pages: 795 - 815 Abstract: Computing the distance between vertices in a large dynamic network is an important task in many real-time applications. An exact real-time computation is often infeasible, due to the network size, dynamic changes and the requirement for rapid response. We hence revert to estimates. One popular method for distance estimation uses a set of vertices, called landmarks, whose distance from all other vertices is computed offline. Then, the online query estimates the distance between two arbitrary vertices by summing the computed distances from the source to a landmark and from the landmark to the target. In this paper we suggest a new method for computing the set of landmarks, based on a sampled set of shortest path trees (SPTs). The SPTs provide a good estimation of the number of shortest paths that a vertex covers, which is strongly correlated with distance estimation error. We provide an extensive set of experiments, comparing the proposed Sampled SPTs method to state of the art, and show that our approach provides lower distance estimation errors on a wide set of benchmarks. We further analyse the time and space complexities of our method, and its sensitivity to the number of the sampled SPTs, as well as the number of landmarks, showing our method to consistently outperforms other approaches. PubDate: 2017-06-09 DOI: 10.1093/comnet/cnx008 Issue No:Vol. 5, No. 5 (2017)