CS Paper Radar

Computational Structure of Pairwise Housing Connectedness Networks

Seo In Jang, Seung Ho Choi, Ji-Eun Shin, Hyunwoo Lee

cs.CE cs.SI ·submitted 2026-11-09 10:45 UTC · v1

Abstract

Directed housing-submarket networks combine common market movement with heterogeneous bilateral relations, and different node-level measures need not yield distinct empirical rankings. We construct a positive pairwise net-connectedness network from the generalized forecast error variance decomposition (GFEVD) of a vector autoregression (VAR) and use it to compare complementary node positions. Net directional connectedness (NET), PageRank, and Viral Centrality summarize net directional balance, recursively weighted incoming position, and normalized multistep reach. When bilateral net differences are nonzero, the network is a weighted tournament. A least-squares edge-flow decomposition separates the pairwise-net matrix into a NET-equivalent gradient component and a NET-orthogonal residual, while a monotone-allocation condition establishes exact PageRank-indegree correspondence in a transitive tournament. In Seoul's 25-district network, the gradient component accounts for 70.9% of the squared Frobenius norm, leaving 29.1% in the residual component. PageRank is strongly aligned with indegree (Spearman $ρ=0.987$), and Viral Centrality with outdegree ($ρ=0.935$); the PageRank alignment exceeds the range of independently weighted simulations with comparable tournament consistency and edge-weight variation. Three common-component treatments reduce total connectedness from 81.98% to 50.60-52.00%, a 36.6-38.3% reduction relative to the raw system, and reverse 97-98 of 300 pairwise net directions. Thus, both the magnitude and the apparent direction of connectedness depend materially on the treatment of citywide common movement. Songpa's positive NET position remains prominent across common-component treatments and dynamic specifications and ranks first in both chronological subsamples.

Comment
56 pages, 6 figures, 16 tables; includes supplementary information

Closest papers

Nearest neighbours by meaning across the whole index.

Semi-Monotonicity for Spectral Centrality Measures

cs.SI ·2026-09-21 ·Paolo Boldi, Davide D'Ascenzo, Flavio Furia, Sebastiano Vigna
theory similarity 0.61
Abstract

Score monotonicity and rank monotonicity are properties describing the behavior of a centrality measure when an arc is added to a network: the former requires that the score of the target of the arc should increase, the latter that its importance with respect to the remaining nodes should not deteriorate. While in directed networks almost all classical centrality measures satisfy both properties, in undirected networks they fail for most measures: adding an edge can reduce the score or the rank of one of its endpoints. Semi-monotonicity is a recently introduced weaker property for undirected networks, requiring that at least one of the two endpoints of the new edge enjoys monotonicity, and it is known to hold for closeness, harmonic centrality, distance-decay centralities and betweenness. In this paper we study semi-monotonicity for three classical spectral centrality measures: eigenvector centrality, Katz's index, and PageRank. We prove that all of them are strictly rank semi-monotone on connected undirected graphs, and that all of them are also score semi-monotone, (the only exception being eigenvector centrality when scores are normalized by projecting the constant vector on the dominant eigenspace, for which we provide a counterexample). In particular, adding an edge can never decrease the PageRank of both its endpoints, which answers a question left open in previous work.

0.19

Link prediction in complex networks via fusing node centrality and local similarity indices: a fair-protocol reassessment and parameter design principles

cs.SI ·2026-09-09 ·Yingying Zhang, Chengye Zhao
benchmark similarity 0.60
Abstract · 34 pages, 13 tables, 6 figures, 50 references

We reassess a published fusion method under a fair protocol. Local similarity indices are cheap but score every node pair without common neighbors zero, and weighting them by a node centrality product, as proposed for PageRank, is not robust once the protocol is made comparable across indices; on our eight-network panel the reported improvement does not survive that protocol for six of the seven local indices. We study these issues in a unified piecewise framework that modulates the local score multiplicatively by a centrality product when local information suffices and uses a small-dose centrality product as a completion term when it does not. A scale analysis and a reassessment on eight real-world networks (five-fold cross-validation, exhaustive negative samples) trace this to the O(n^-2) scale of the PageRank product, whose modulation factor is then a near-identity map, and to its rank correlation with degree exceeding 0.89; control arms show scale calibration is necessary but not sufficient. The min-max normalized DomiRank product instead has an O(1) range and substantial non-degree content, and a grid search yields unified parameters (omega=5, c=0.1) under which DR-JC/HPI/SO significantly outperform their local baselines already at the dataset level (p=0.027 and 0.035), the remaining four at the fold level only; DR-RA attains an average AUC of 0.9257, above nine of ten comparison methods, whereas degree-only preferential attachment reaches only 0.7736. Mechanism decomposition shows the two mechanisms contribute differently across index families and should be dosed separately, yielding a safety boundary 0 < c <= 0.3, a plateau omega in [0.5, 12] and a near-critical plateau sigma in [0.7, 0.95]. Two negative results bound the claim: under a degree-corrected benchmark the gains over local baselines vanish and reverse in sign, and the AUC gains do not translate into top-L hit rate.

0.16

Theoretical relations between basic centrality measures in real-world networks

cs.SI math.CO ·2026-11-01 ·Mikhail Tuzhilin
similarity 0.58
Abstract

We establish new relationships among several fundamental measures of real-world networks, including the average clustering coefficient, the global clustering coefficient, the average shortest-path length and degree centrality, closeness centrality, betweenness centrality and ksi-centrality. We further develop the theory of $j$-neighborhood centrality, which encompasses degree centrality and ksi-centrality as special cases.

0.14

Comparing Probabilistic Influence-Spreading Centralities to Commonly-Used Centrality Measures in Directed and Weighted Networks

cs.SI ·2026-08-19 ·Juuso Luhtala, Vesa Kuikka, Kimmo K. Kaski
similarity 0.57
Abstract

The Influence-Spreading Model (ISM) introduces three probabilistic centrality measures: out-centrality, in-centrality, and ISM betweenness centrality. Out-centrality measures the average probability that a node influences others, while in-centrality measures the average probability that others influence a node. ISM betweenness centrality measures the change in total probabilistic influence when a node is removed. These measures depend on edge transmission probabilities and allow walks up to a specified maximum length. We compare the ISM centrality measures to commonly used weighted variants of out-degree, in-degree, closeness, shortest-path betweenness, and Katz centrality in directed, weighted networks using four real-world online social networks and nine synthetic networks generated by Erdős-Rényi, navigable small-world, and directed scale-free models. For the synthetic networks, the edge probabilities are drawn from three beta distributions. We evaluate the similarity in centrality values and their ranking using Pearson correlation and Spearman's rank correlation coefficients. Results show strong correlations between the ISM out-centrality and weighted out-degree and outward Katz centrality, particularly for low edge probabilities. Conversely, relationships between the ISM in-centrality and other measures vary with network topology, sometimes yielding negative correlations. Correlations between the ISM betweenness and the shortest-path betweenness are also topology-dependent and weaken as alternative influence paths become more relevant. Overall, standard centrality measures can approximate the influence of broadcasting influence but often miss the nuances of receiving influence and probabilistic intermediary roles.

0.18

Spectral Efficiency Centrality: An Efficient Spectral Approach for Influential Node Identification in Temporal Networks

cs.SI ·2026-08-14 ·Aksa Urooj, Iqra Altaf Gillani
similarity 0.56
Abstract · 23 pages, 16 figures, 11 tables, journal paper

Centrality measures play a vital role in identifying influential nodes in evolving networks. While existing temporal centrality measures primarily rely on local structural properties or temporal paths, spectral node-removal approaches have been largely limited to static networks. To bridge this gap, we propose Spectral Efficiency Centrality (SEC), a temporal spectral centrality framework that quantifies node importance by evaluating the change in spectral radius caused by node removal across temporal snapshots. By capturing the global structural influence of nodes throughout network evolution, SEC identifies nodes that are critical for preserving the structural connectivity and efficiency of temporal networks. To improve computational scalability, we further develop an efficient approximation, ASEC, based on Perron-Frobenius theory and first-order eigenvalue perturbation. ASEC requires only the leading eigenpair and avoids repeated eigendecomposition, making it suitable for large temporal networks. Extensive experiments on multiple real-world temporal datasets demonstrate that SEC and ASEC outperform existing baseline centrality measures in identifying influential nodes under SI, SIS, and IC diffusion models. Statistical significance and robustness analyses further confirm their effectiveness, while ASEC offers a computationally efficient solution for large-scale temporal networks.

0.10

Testing Central Structure for Complex Networks

cs.LG ·2026-10-11 ·Qilong Wu, Yuxiao Li, Simeng Zhang, Xinying Liu, Yan Liu +1 more
similarity 0.55
Abstract · 12 pages, 4 figures, submitted to Chaos, Solitons & Fractals

Centrality measures rank nodes even when the observed differences can be explained by ordinary structural variation. We therefore study a preceding question: whether a network contains a statistically identifiable central structure at all. We formulate this question as a network-level hypothesis testing issue using the adjacency spectral radius as the test statistic and estimate an empirical p-value from randomized networks generated under a specified null model. The framework is evaluated using G(N,M), Chung-Lu, and two implementations of the configuration model on simulated benchmarks and 55 real networks. Controlled experiments further vary the number and connection weights of designated central nodes while holding network size and density fixed. The results show a clear negative association between central-structure strength and the empirical p-value. They also demonstrate that rejection decisions depend substantially on the structural properties preserved by the null model: the detected network sets are not simply nested across models.

0.29

Edge-based Katz centralities for spatio-temporal multiplex networks

cs.SI math.NA ·2026-09-21 ·Kai Bergermann, Francesco Gravili, Valeria Simoncini, Martin Stoll
similarity 0.55
Abstract

Katz centrality is a well-established measure to identify and rank the most important nodes in complex networks by means of a linear system solve. Recent works have developed notions of Katz centrality for temporal, i.e., time-evolving networks. Their drawback is that small changes in the network structure may drastically change centralities across large parts of the network. Moreover, an unproportional effort in the network science community has been devoted to the study of node-based quantities while edge-based measures are far less explored. In this manuscript, we introduce a novel failure-aware temporal multiplex network model for computing edge-based Katz centralities for spatial networks. This class of networks admits the use of the line graph as network representation. We use a block-triangular and -banded supra-adjacency matrix representation, modeling inter-layer connections as low-rank matrices, which assigns a spatially constrained emphasis on up- or downdated edges. These could represent, e.g., breakages of water/gas pipes or obstructions in street networks in real-time infrastructure monitoring applications. We analyze the structure of the of the block matrix inverse with respect to entry decay in the blocks above the block-diagonal. This gives rise to two truncation approaches that allow drastic computational runtime reductions at the cost of introducing a controlled truncation error. Numerical experiments on a range of real-world spatio-temporal networks of size up to $2\cdot 10^8$ illustrate accuracy and efficiency with runtime gains of up to a factor of $679$.

0.26

Disparity in Influence: A Fairness Evaluation of Centrality Measures in Complex Networks

cs.SI ·2026-11-15 ·Kirtidev Mohapatra, Harsh Vardhan Singh, Rishi Ranjan Singh, Akrati Saxena
similarity 0.54
Abstract

Social networks are shaped by homophily-driven connections, which naturally lead to the emergence of communities with uneven sizes and influence. Such structural imbalances impact the fairness of network analysis tools, particularly centrality measures that are widely used to identify influential nodes for tasks like information diffusion and network robustness. In this work, we conduct a comprehensive assessment of fairness in centrality measures, using influence spreading across networks with heterogeneous community structures. We first analytically show that disparity is bounded by outreach; cross-community outreach is bounded by the inter-community cut; and when all seeds lie in one community, disparity approaches the normalized outreach within that community as cross-community transmission vanishes. This explains why attenuation concentrates influence in the community where diffusion starts. We further evaluate a broad spectrum of centrality measures, including local, semi-local, global, and community-aware measures, on both synthetic network generative models and real-world datasets, using the Independent Cascade and Linear Threshold Models. The results consistently show that influence tends to concentrate within larger communities, with disparities becoming more pronounced under constrained or deterministic diffusion settings. We further observe that fairness is highly sensitive to the choice of centrality measure rather than its general category. In particular, fairness-aware adaptations of PageRank demonstrate a strong balance between maximizing influence reach and maintaining equitable distribution across communities. On real networks, these conclusions are largely stable under random removal or addition of up to 3% of the edges. Our findings highlight the need to explicitly account for fairness when designing and selecting centrality-based strategies in networked systems.

0.19