Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe localization of non-backtracking centrality in networks and its physical consequences
138
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The spectrum of the non-backtracking matrix plays a crucial role in determining various structural and dynamical properties of networked systems, ranging from the threshold in bond percolation and non-recurrent epidemic processes, to community structure, to node importance. Here we calculate the largest eigenvalue of the non-backtracking matrix and the associated non-backtracking centrality for uncorrelated random networks, finding expressions in excellent agreement with numerical results. We show however that the same formulas do not work well for many real-world networks. We identify the mechanism responsible for this violation in the localization of the non-backtracking centrality on network subgraphs whose formation is highly unlikely in uncorrelated networks, but rather common in real-world structures. Exploiting this knowledge we present an heuristic generalized formula for the largest eigenvalue, which is remarkably accurate for all networks of a large empirical dataset. We show that this newly uncovered localization phenomenon allows to understand the failure of the message-passing prediction for the percolation threshold in many real-world structures.
rate research
Read More
Community detection or clustering is a crucial task for understanding the structure of complex systems. In some networks, nodes are permitted to be linked by either positive or negative edges; such networks are called signed networks. Discovering communities in signed networks is more challenging than that in unsigned networks. In this study, we innovatively develop a non-backtracking matrix of signed networks, theoretically derive a detectability threshold for this matrix, and demonstrate the feasibility of using the matrix for community detection. We further improve the developed matrix by considering the balanced paths in the network (referred to as a balanced non-backtracking matrix). Simulation results demonstrate that the algorithm based on the balanced nonbacktracking matrix significantly outperforms those based on the adjacency matrix and the signed non-backtracking matrix. The proposed (improved) matrix shows great potential for detecting communities with or without overlap.
The spectral properties of the adjacency matrix, in particular its largest eigenvalue and the associated principal eigenvector, dominate many structural and dynamical properties of complex networks. Here we focus on the localization properties of the principal eigenvector in real networks. We show that in most cases it is either localized on the star defined by the node with largest degree (hub) and its nearest neighbors, or on the densely connected subgraph defined by the maximum $K$-core in a $K$-core decomposition. The localization of the principal eigenvector is often strongly correlated with the value of the largest eigenvalue, which is given by the local eigenvalue of the corresponding localization subgraph, but different scenarios sometimes occur. We additionally show that simple targeted immunization strategies for epidemic spreading are extremely sensitive to the actual localization set.
Complex networks or graphs provide a powerful framework to understand importance of individuals and their interactions in real-world complex systems. Several graph theoretical measures have been introduced to access importance of the individual in systems represented by networks. Particularly, eigenvector centrality (EC) measure has been very popular due to its ability in measuring importance of the nodes based on not only number of interactions they acquire but also particular structural positions they have in the networks. Furthermore, the presence of certain structural features, such as the existence of high degree nodes in a network is recognized to induce localization transition of the principal eigenvector (PEV) of the networks adjacency matrix. Localization of PEV has been shown to cause difficulties in assigning centrality weights to the nodes based on the EC. We revisit PEV localization and its relation with failure of EC problem, and by using simple model networks demonstrate that in addition to the localization of the PEV, the delocalization of PEV may also create difficulties for using EC as a measure to rank the nodes. Our investigation while providing fundamental insight to the relation between PEV localization and centrality of nodes in networks, suggests that for the networks having delocalized PEVs, it is better to use degree centrality measure to rank the nodes.
Understanding the causes and consequences of, and devising countermeasures to, global warming is a profoundly complex problem. Even when researchers narrow down the focus to a publishable investigation, their analysis often contains enough interacting components to require a network visualization. Networks are thus both necessary and natural elements of climate science. Furthermore, networks form a mathematical foundation for a multitude of computational and analytical techniques. We are only beginning to see the benefits of this connection between the sciences of climate change and networks. In this review, we cover use-cases of networks in the climate-change literature -- what they represent, how they are analyzed, and what insights they bring. We also discuss network data, tools, and problems yet to be explored.
There are different measures to classify a networks data set that, depending on the problem, have different success. For example, the resistance distance and eigenvector centrality measures have been successful in revealing ecological pathways and differentiating between biomedical images of patients with Alzheimers disease, respectively. The resistance distance measures the effective distance between any two nodes of a network taking into account all possible shortest paths between them and the eigenvector centrality measures the relative importance of each node in the network. However, both measures require knowing the networks eigenvalues and eigenvectors -- eigenvectors being the more computationally demanding task. Here, we show that we can closely approximate these two measures using only the eigenvalue spectra, where we illustrate this by experimenting on elemental resistor circuits and paradigmatic network models -- random and small-world networks. Our results are supported by analytical derivations, showing that the eigenvector centrality can be perfectly matched in all cases whilst the resistance distance can be closely approximated. Our underlying approach is based on the work by Denton, Parke, Tao, and Zhang [arXiv:1908.03795 (2019)], which is unrestricted to these topological measures and can be applied to most problems requiring the calculation of eigenvectors.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
