2026· ITEGAM- Journal of Engineering and Technology for Industrial Applications (ITEGAM-JETIA)· 0 citations
TL;DR
Experimental results demonstrate that TWJtr-D significantly reduces computation time and outperforms state-of-the-art methods which process in a similar pattern, highlighting the efficiency of TWJtr-D for triangle detection in large-scale networks.
Abstract
During the past decades, the world shifted towards online transactions. From data exchange, service provision to business, users and providers rely on the internet and social networks as a common platform for sharing and trading. In order to ensure an effective and reliable management of these networks and the flow of information within them, it is essential to detect user profiles and communities. In that context, triangle detection is a fundamental task in network analysis, as triangles are the smallest structure in a community. However, identifying triangles in large-scale and dense networks is a heavy and highly time-consuming treatment, due to costly neighborhood intersection computations. Our research aims to optimize intersection computation by minimizing the number of comparisons performed, avoid triangle duplication throughout the detection process and thus reducing the overall computation time. The method we propose, Test With Jumps for triangle detection without duplicates (TWJtr-D), is a refined version of Test With Jumps for triangle detection (TWJtr) algorithm. It optimizes intersection computing between neighbors sorted lists while avoiding redundant comparisons and duplicated triangles. Experimental results, on real-world datasets, demonstrate that TWJtr-D significantly reduces computation time and outperforms state-of-the-art methods which process in a similar pattern. This highlights the efficiency of TWJtr-D for triangle detection in large-scale networks. Future work will upgrade this method to parallel processing to rank its efficiency among algorithms in the same field.
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 survey will help researchers better understand and gain useful insights into the large and complex design space of out-of-core graph processing, including graph preprocessing, graph algorithm execution, utilization of emerging storage devices, and miscellaneous optimizations.
Computing betweenness centrality on large networks is inherently expensive, as it requires aggregating shortest-path dependencies across all pairs of vertices and becomes increasingly difficult to scale as network size grows. Scalable distributed algorithms can facilitate such computations, particularly when centralised processing is not feasible, and message exchanges must be carefully controlled, for example, in bandwidth-limited or very large-scale networks. However, existing distributed betweenness centrality implementations do not integrate a lightweight, system-wide termination detector. As a consequence, this can lead to extra messaging after local convergence or, if misconfigured, premature stops. In this work, a lightweight, system-wide global termination detection algorithm for this task is presented. The proposed method enables vertices to decide locally when the overall system has converged. The method is evaluated against a local stopping strategy in which vertices terminate individually once their own estimates stabilise. To compare these two approaches, namely global termination detection and local stopping, a custom Python simulator is implemented, and both approaches are tested on synthetic (Erdos-Renyi and geometric) and real (Email and Road) network topologies. Our results show that system-wide termination detection lets vertices stop safely after detecting global convergence, as indicated by zero final error in the evaluated networks, rather than stopping independently based only on local convergence. The local stopping approach, on the other hand, results in premature termination and some errors on heterogeneous networks. This work emphasises the need for coordinated halting in distributed centrality computation.
Siamak Abdi, Lucia Cavallaro, G. D. Fatta· 0 citations
The findings indicate that the Eppstein-Wang algorithm provides a practical and scalable solution for average distance estimation, with higher reliability on unipartite graphs compared to bipartite graphs.
Cohesive subgraph mining is a fundamental task in graph data analytics. We re-visit the problem of listing all minimal $k$-cores, where a $k$-core is a subgraph in which every vertex has degree at least $k$, and minimality requires that no proper subset remains a $k$-core. Existing methods are computationally prohibitive due to explosive branching and costly branch state update, leading to the trivial worst-case bound $O^{*}\left(2^{n}\right)$ for the basic branch-and-bound baseline wh, where $O^{*}$ suppresses polynomial factors and $n$ is the number of vertices. In this paper, we present an improved method IMinC based on three key ideas: (i) a principled branching state with lineartime update; (ii) a pivot strategy that guides branching toward promising vertices; and (iii) a divide-and-conquer framework that initializes each subproblem to enable our pivot strategy throughout and reduce recursion depth. We further introduce three reduction rules that aggressively prune infeasible branches. Together, these components yield the worst-case time complexity of $O^{*}\left(\alpha_{\ell}^{n}\right)$, where $\alpha_{\ell}$ is a positive number strictly smaller than 2. We also extend IMinC to list minimal $k$-cores under a size bound, addressing practical needs such as size-bounded community search. Extensive experiments on 12 real-world graphs demonstrate that IMinC outperforms the baselines by up to 2 order of magnitude, delivering substantial gains in efficiency.
Yukai Sun, Kaiqiang Yu, Shengxin Liu et al.· IEEE International Conferenc...· 0 citations