Research

Working Papers

Constrained graph generation: Preserving diameter and clustering coefficient simultaneously

Dávid Ferenczi, Alexander Grigoriev

Generating graphs subject to strict structural constraints is a fundamental computational challenge in network science. Simultaneously preserving interacting properties—such as the diameter and the clustering coefficient— is particularly demanding. Simple constructive algorithms often fail to locate vanishingly small feasible regions within the highly constrained configuration space, while traditional Markov Chain Monte Carlo (MCMC) samplers suffer from severe ergodicity breaking. In this paper, we propose a two-step hybrid framework combining Ant Colony Optimization (ACO) and MCMC sampling. First, we design a layered ACO construction heuristic to perform a guided global search, effectively locating valid graph structures. Second, we use these discovered configurations as structurally distinct seed states for an MCMC rewiring algorithm. We evaluate this framework across multiple edge densities and constraint regimes. Using the spectral distance of the normalized Laplacian to quantify structural diversity, our experiments reveal a stark contrast between the methods. Standard MCMC samplers remain rigidly trapped in isolated regions around their initial seeds. Conversely, our hybrid ACO-MCMC approach successfully bridges disconnected configuration landscapes, generating a vastly richer and structurally diverse set of valid graphs.

Inferring signed social networks from contact patterns

Dávid Ferenczi, Jean-Gabriel Young, Leto Peel

Social networks are typically inferred from indirect observations, such as proximity data; yet, most methods cannot distinguish between absent relationships and actual negative ties, as both can result in few or no interactions. We address the challenge of inferring signed networks from contact patterns while accounting for whether lack of interactions reflect a lack of opportunity as opposed to active avoidance. We develop a Bayesian framework with MCMC inference that models interaction groups to separate chance from choice when no interactions are observed. Validation on synthetic data demonstrates superior performance compared to natural baselines, particularly in detecting negative edges. We apply our method to French high school contact data to reveal a structure consistent with friendship surveys and demonstrate the model's adequacy through posterior predictive checks.