Complex Network Analysis Techniques

Latest papers

• Who Belongs Together? Topical and Social Structure in Bluesky Starter Packs

  Sima Adleyba, Onur Varol · 28 September 2026

  Bluesky starter packs are human curated collections of accounts and feeds aimed at helping users discover new communities, especially during onboarding. Prior research has examined their effects on platform growth and account visibility. However, whether these packs capture meaningful topical and so…

• Diffusion-Induced Spatial Attention Overlapping Community Detection

  Kosti Koistinen, Vesa Kuikka, Joni Herttuainen, Matthew Hendren, Brian Holt, Kimmo K. Kaski · 23 September 2026

  Detection of overlapping communities is essential for modelling networks in which nodes participate simultaneously in multiple structural or functional groups. Existing graph neural network approaches commonly rely on local message passing, which can obscure community boundaries through smoothing an…

• Partially Observed Sparse Graphs: The Unknown Sampling Rate is a Tail Index

  Jian Xu, Delu Zeng, John Paisley, Qibin Zhao · 23 September 2026

  A large graph is often available only in part: a crawl stopped by its budget, a panel, a partial dump. When the sampled fraction $s$ is known by design the total edge count follows from $\hat e=e_s/s^2$ and no model is needed. We treat the case where $s$ is unknown and the population size is known. …

• Towards Adaptive Federated Graph Clustering: A Global Community-aware Contrastive Learning-based Approach

  Yinlin Zhu, Di Wu, Wang Luo, Guocong Quan, Miao Hu · 23 September 2026

  Federated graph learning (FGL) enables multiple clients to collaboratively train graph models without sharing their private graph data, providing a promising paradigm for mining knowledge from distributed graph repositories. While most existing FGL methods focus on supervised tasks, real-world graph…

• Optimal and heuristic strategies for evaluating the influence of coordinated behavior in information cascades and retweet networks

  Niccol\`o Di Marco, Matteo Cinelli, Shinichi Nakano, Andrea Frosini · 22 September 2026

  Coordinated Inauthentic Behavior (CIB) has become a major concern in online social platforms, yet its actual impact on information diffusion remains poorly understood. Existing research has primarily focused on detecting coordinated activity, while comparatively little attention has been devoted to …

• Towards stratified sampling for redistricting plans

  Zijian Wang, Gregory J. Herschlag, Joon-Hyeok Yim, Jonathan C. Mattingly, Anna C. Gilbert · 17 September 2026

  Rapid algorithmic developments have accelerated the sampling of redistricting ensembles (balanced graph partitions), yet evaluating rare events and sampling complex target measures remains a core challenge due to the high-dimensional and combinatorial nature of the phase space. We address a prerequi…

• netseg: a Python Package for Measuring Structural Polarization and Segregation in Social Networks

  Onur Tuncay Bal, Micha{\l} Bojanowski · 16 September 2026

  The study of structural polarization and segregation in social networks is an established line of research, and the quantification of both phenomena proceeds through a set of widely cited network indices. The code implementing those indices, however, is seldom released and almost never tested. We pr…

• Edge-addition monotonicity of positive p-energy fails for every p >= 1

  Koyar Afrasyab · 15 September 2026

  At a 2021 AIM workshop, Guo conjectured that the positive square energy s+ = E+_2 should inherit the familiar edge-addition monotonicity of the spectral radius, rho(G + uv) >= rho(G). That conjecture was subsequently shown to fail at p = 2. Tang, Liu, and Wang then introduced positive p-energy, prov…

• From Network Inequality to Network Fairness: A Perspective on Responsible Decision-Making

  Lisette Esp\'in-Noboa, Tina Eliassi-Rad, Pak-Hang Wong, Erich Prem, Meike Zehlike, Ricardo Baeza-Yates, Suresh Venkatasubramanian, Fariba Karimi · 15 September 2026

  Social networks shape how individuals make decisions and how opportunities are distributed. However, the mechanisms that generate these networks often reflect pre-existing inequalities, and technologies that rely on network-derived signals risk further amplifying such disparities. Algorithmic fairne…

• When Connected Does Not Mean Similar: Charting the Homophily Boundary of SNAP-KG for Streaming Entity Integration

  Jui-Chien Lin, Oshani Seneviratne · 14 September 2026

  SNAP-KG is a framework for assigning newly arriving entities to semantic communities in a growing knowledge graph (KG) using only their raw features, with no graph access and no retraining at inference time. It was evaluated on five multi-view benchmarks and a 2.4M-node OGB-WikiKG2 KG. In each of th…

• SynCo: Synthetic Community-Aware Attributed Graph Generator for Graph Neural Network Benchmarking

  Guilherme Henrique Messias, Mariana Caravanti de Souza, Sylvia Iasulaitis, Alan Dem\'etrius Baria Valejo · 11 September 2026

  Graph Neural Networks (GNNs) are powerful models for handling attributed graphs in tasks such as classification, link prediction, and community detection, as they enable the aggregation of information from both structural and semantic sources. However, progress in community detection is hindered by …

• Robustness of shallow graph embedding methods for community detection

  Zhi-Feng Wei, Pablo Moriano, Ramakrishnan Kannan · 10 September 2026

  This study investigates the robustness of shallow graph embedding methods for community detection in the face of network perturbations, specifically node deletions. Graph embedding techniques, which represent nodes as low-dimensional vectors, are widely used for various graph machine learning tasks …

• CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs

  Meher Chaitanya, Cameron Musco, Aristides Gionis · 10 September 2026

  Graph-data workloads such as diffusion estimation, ranking, semi-supervised learning, and network optimization often solve many Laplacian or symmetric diagonally dominant M-matrix (SDDM) systems with the same coefficient matrix. Approximate Cholesky preconditioners eliminate vertices one at a time a…

• Statistical Feature Augmentation for Anomaly Detection in Dynamic Graphs

  Philipp Schlinge, Jean-Luc Schnipper, Martin Atzmueller · 4 September 2026

  Dynamic networks are being applied in many domains, from social media to logistics systems, each with their own set of special characteristics. A model employed on this type of data must capture the duality between temporal/structural and feature-based information. Yet state-of-the-art deep learning…

• Selective Hypergraph Refinement for Frozen Graph Clustering

  Zimo Si · 4 September 2026

  Existing graph-clustering methods typically improve clustering performance by optimizing model parameters and node representations. Effective means of further improving the clustering results of an already trained and frozen model, however, remain limited. We study post-processing for frozen graph c…

• Evaluating GNNs for Success Prediction in Artist Collaboration Networks

  Wiktor Dowgia{\l}{\l}o · 4 September 2026

  As the music industry becomes an increasingly collaborative effort, understanding the underlying structures of the artist network has become a focal point in cultural data analytics. This study expands on the previous analyses of the Italian and Danish networks by introducing a novel dataset of the …

• A Network Science Perspective on Evaluating Deep Graph Generative Models

  Tianrui Mao, Abele Malan, Megha Khosla, Lydia Chen, Huijuan Wang · 2 September 2026

  Traditional network models from network science, such as the Erdos-Renyi and configuration models, generate random networks that reproduce few selected topological properties observed in real-world networks. Deep graph generative models emerge as a data-driven approach, leveraging deep neural networ…

• MDTE: Minority-Aware Diffusion over Temporal Edge Events for Imbalanced Node Classification

  Zhou Zelong, Zhang Tianming, Yang Zhengyi, Tang Yifu, Hou Chenyu, Cao Bin, Fan Jing · 26 August 2026

  Class-imbalanced node classification on temporal graphs is challenging because majority-dominated temporal propagation progressively assimilates minority representations, while conventional node and neighborhood information provides insufficient discriminative evidence for minority classes. To addre…

• Multi-Source Wasserstein Distributionally Robust Graph Learning

  Chuansen Peng, Yifan Xia, Jinshan Zhong, Xiaojing Shen · 21 August 2026

  Network topology inference from graph signals is central to graph signal processing with applications in neuroscience, sensor, and social networks. In practice, target-domain samples are scarce while heterogeneous source-domain data are abundant. Fusing these sources is challenging: Euclidean averag…

• A Network-driven Framework for Public Event Forecasting via Dynamic Interaction Network Evolution

  Jie Wei, Yue Liu, Xiaochuan Tang, Biao Cai, Xiangtao Li, Yanmei Hu · 18 August 2026

  Effective public event forecasting is essential for intelligent service systems, enabling proactive risk management, adaptive resource allocation, and timely decision-making. In many real-world scenarios, the evolution of public events is driven by dynamic interactions among participants. Motivated …

• Adjacency-Based Spectral Proxy Control of Mobile Communication Agents

  Mariana del Castillo, Federico Larroca · 17 August 2026

  We consider a heterogeneous mobile-agent network composed of uncontrolled task agents and controllable communication agents. The objective is to reposition communication agents online as task agents move. Since throughput-based objectives are generally unsuitable for real-time control, spectral grap…

• High-dimensional networks and mean squared error for possibly misspecified models

  Lourens Waldorp · 14 August 2026

  To avoid missing important variables and their connections in networks, more and more variables are included in network analysis. Here we show that in a setting with many more parameters than observations (high-dimensional) it is possible to get a conservative (i.e., low false positive rate) estimat…

• Spectral graph clustering with inhomogeneous latent geometry

  Konstantin Avrachenkov, Lucas S. Sibemberg, Alexander Van Werde · 13 August 2026

  We study spectral clustering in the presence of a confounding latent geometry. The leading eigenvectors may then be dominated by the latent geometry rather than by the communities. Nevertheless, we show in a block latent-space model that communities can be recovered from eigenvectors deeper in the s…

• Spectral Embeddings of Degree-$\alpha$ Laplacians in Random Dot Product Graphs

  John Park, Ning Hao · 12 August 2026

  Spectral clustering methods for network data are commonly based on a few matrix representations, such as the adjacency matrix and the symmetric Laplacian. We study a continuum of degree-normalized spectral embeddings that includes these commonly used choices as special cases. Under a random dot prod…

• Unveiling the Predators: Contemporary Approaches to Identifying Illegitimate Open Access Journals in the Academic Publishing Ecosystem

  Robert \v{S}am\'arek, Radek Martinek · 12 August 2026

  Predatory journals pose a significant challenge to the integrity of the Open Access (OA) publishing model by exploiting its framework for financial gain while bypassing essential editorial and peer-review standards. This study critically evaluates existing methodologies for identifying such journals…