Jun 2026· arXiv.org· Vol abs/2606.26608· 0 citations· 47 references
Computer Science
TL;DR
A novel algorithm GSCF is proposed, built on a variant of loop-erased random walks, to generate generalized spanning converging forests in expected O(n) time and two sampling algorithms are developed, FMDE and FMDE+, for estimating the diagonal of the forest matrix.
Abstract
The forest matrix of a signed graph plays an important role in network science and social opinion dynamics, yet existing algorithms are mainly designed for unsigned graphs and are difficult to extend to signed graphs. In this paper, we study the problem of efficiently estimating the forest matrix of signed graphs with n nodes and introduce the signed forest matrix theorem, which establishes the relationship between generalized spanning converging forests and the forest matrix. Based on this result, we propose a novel algorithm GSCF, built on a variant of loop-erased random walks, to generate generalized spanning converging forests in expected O(n) time. We further develop two sampling algorithms, FMDE and FMDE+, for estimating the diagonal of the forest matrix, both with time complexity O(ln), where l is the number of samples. Extensive experiments on various signed graphs show that our methods achieve high estimation accuracy, significantly improve computational efficiency, and scale to graphs with over twenty million nodes. Our source code is publicly available on https://github.com/HaoxinSun98/SignedForestDiagonal.
Learning on signed graphs poses unique challenges due to the presence of both positive and negative links, which represent complex social dynamics such as trust and conflict. While existing signed graph neural networks (SGNNs) have achieved promising results, most rely on deep, multi-hop propagation architectures that suffer from scalability issues. In this work, we revisit message passing from the perspective of opinion dynamics, and propose SigFJProp, a novel and lightweight SGNN framework inspired by the Friedkin–Johnsen model. SigFJProp models signed message propagation as a discrete-time opinion update process, whose equilibrium state admits a closed-form solution involving the signed forest matrix. To make this computation tractable on large-scale graphs, we introduce Expansion Forest Sampling, a linear-time approximation method tailored for signed networks. Our approach decouples neural representation learning from propagation dynamics, enabling efficient and interpretable learning. Experimental results on seven benchmark datasets, including one with over 750K nodes and 10M edges, demonstrate that SigFJProp achieves competitive or superior performance compared to state-of-the-art methods, while significantly reducing computational overhead. The code is available at https://github.com/SunYubo23/SigFJProp.
Yubo Sun, Haoxin Sun, Zhongzhi Zhang· Proceedings of the 32nd ACM...· 0 citations
A novel heuristic community detection algorithm, termed CoDeSEG, which identifies communities by minimizing the network's two-dimensional structural entropy within a potential game framework, and introduces a structural entropy-based node overlapping heuristic for detecting overlapping communities, with a near-linear time complexity.
This paper presents a comparative analysis of two variants of a classical algorithm for finding the shortest path in a connected graph. The first variant uses an adjacency matrix (AM) to verify the existence of an edge (arc) between two vertices, while the second variant performs the same verification using an adjacency list (AL). The objective of this study is to examine how graph density affects the performance of the two algorithmic modifications depending on the data structure used. A total of 95 graphs were analyzed, grouped into five sets from 100 to 500 in increments of 100. For each group, 19 graphs were generated with densities ranging from 5% to 95% in increments of 5%. The methodology includes analyzing the number of iterations, assignments, and comparisons executed by the algorithms for all graphs. The initial hypothesis assumed that the total number of operations would always be lower when using an AL instead of an adjacency matrix, regardless of graph density. The results demonstrate that this assumption is incorrect: for densities above 82%, the total number of operations is lower when using an adjacency matrix, whereas the AL is more efficient for densities below 82%, with its efficiency increasing as density decreases. These findings are particularly important for mobile technologies, as they support the design of more efficient pathfinding solutions that optimize performance and energy consumption in mobile applications.
V. Kralev, Radoslava Kraleva, Aleksandra Popova· International Journal of Int...· 0 citations
The joint asymptotic distribution of any finite collection of network moments in random graphs sampled from a graphon, which includes both the nondegenerate case as well as the degenerate case, provides the higher-order fluctuation theory for subgraph counts in the graphon model.
Anirban Chatterjee, S. Dan, B. Bhattacharya· Annals of Statistics· 0 citations
The novel Radial Graphlet Distribution Distance is effective, and comparable in performance to state-of-the-art methods, and the easy-to-compute Joint Degree Distance is a viable alternative to graphlet-based distances, especially for measuring randomness in sets of very large networks.
Bram Mornie, D. Colle, P. Audenaert et al.· Computing· 0 citations
This study explores the spectral characteristics and energy distributions associated with selected graph operations derived from the first Zagreb, second Zagreb, and sum-connectivity matrices to contribute to understanding how algebraic operations induce spectral energy shifts analogous to perturbations in physical or molecular graph systems.
S. Sripriya, A. Anuradha· Baghdad Science Journal· 0 citations