Fast Estimation for Forest Matrix of Signed Graphs

SigFJProp: Lightweight and Scalable Signed Graph Learning via Opinion Dynamics

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.

Comprehensive, Efficient Large-Scale Community Detection via Structural Entropy Game

Community detection is a critical task in graph theory, social network analysis, and bioinformatics, where communities are defined as clusters of densely interconnected nodes. However, detecting communities in large-scale networks with millions of nodes and billions of edges remains challenging due to the inefficiency and unreliability of existing methods. Moreover, many existing methods are limited to specific types of graph structures (such as unweighted or undirected graphs) or are designed solely for detecting static communities, reducing their broader applicability. To address these issues, we propose a novel heuristic community detection algorithm, termed CoDeSEG, which identifies communities by minimizing the network's two-dimensional (2D) structural entropy within a potential game framework. In the game, nodes decide to stay in the current community or move to another based on a strategy that maximizes the 2D structural entropy utility function. Additionally, we introduce a structural entropy-based node overlapping heuristic for detecting overlapping communities, with a near-linear time complexity. Furthermore, we design a cascading influence propagation-based adaptive community update strategy, which dynamically identifies and processes nodes whose community affiliations may change during graph evolution, thereby effectively extending CoDeSEG to dynamic community detection scenarios. Experimental results on fourteen large-scale networks demonstrate that CoDeSEG achieves state-of-the-art performance across three community detection tasks (overlapping, non-overlapping, dynamic), while also delivering substantial improvements in detection efficiency.

Evaluating the Influence of Graph Density on the Efficiency of Shortest Path Algorithms Using Different Data Structures

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.

Higher-order graphon theory: Fluctuations, degeneracies and inference

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.

Quantifying randomness in complex graph sets using pairwise graph distances

A Spectral Approach to Join Based Operations on Graphs

The success of Spectral Graph Theory is due to its immense applications in several fields of science and technology. The parameter `graph energy' plays a significant role in the Hückel Molecular Orbital Theory, where it is used to approximate the total π -electron energy of conjugated hydrocarbons. Several modified versions of the energy parameter have been defined by many researchers depending on the context. 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. When the adjacency matrix provides information only on the existence of a relation among vertex pairs, these refined matrices give more information and weightage to the relation. These matrix-based energies quantify the total spectral energy of a system and provide insight into how structural modifications affect global stability and information distribution. The characteristic polynomials and corresponding eigenvalue spectra of the central graph are obtained for each matrix type, revealing how the spectral measures evolve under structural transformation. The analysis is further extended to the Indu–Bala product of graphs, a non-commutative operation that intricately merges the structural components of two graphs. The explicit expressions for the characteristic polynomial and spectral energies are derived, illustrating the effect of graph composition on spectral distribution. Additionally, for the operations of double-duplication and duplication vertex-join, the closed-form relations for the Zagreb and sum-connectivity spectra and their corresponding energy values are presented. The obtained results contribute to understanding how algebraic operations induce spectral energy shifts analogous to perturbations in physical or molecular graph systems.