Nearest Graph Laplacians with Prescribed Connected Components: A Convex Framework for Network Reconstruction

Abstract

We study the problem of constructing the nearest graph Laplacian matrix to a given Laplacian while enforcing a prescribed connected-component structure. Let the vertex set be partitioned into nonempty disjoint blocks $C_1,\ldots,C_k$, and let $U=[u_1,\ldots,u_k]$ be the matrix of the corresponding block-indicator vectors. The constraint $MU=0$ ensures that these prescribed indicators lie in the nullspace of the optimized Laplacian $M^\star$, and hence the associated graph has at least $k$ connected components. To guarantee exactly the prescribed components, we impose additional block-connectivity constraints on the principal blocks $M_j=M[C_j,C_j]$. These constraints ensure that each prescribed block induces a connected weighted subgraph. The resulting problem is a convex semidefinite optimization problem with a strictly convex Frobenius-norm objective. We prove existence and uniqueness of the minimizer and show that the optimized Laplacian has exactly the prescribed connected components, with nullspace $\operatorname{span}\{u_1,\ldots,u_k\}$. The framework proposed in this work provides a principled tool for quantifying the minimum structural intervention required to transform a graph-based network into one having a prescribed group-separated structure. Numerical examples, including the Sampson monastery positive-affection network, illustrate the nearest faction-consistent weighted reconstruction and the minimum Laplacian perturbation required to realize the prescribed faction structure.

Disclosure

“the optimized graph has no edges between distinct prescribed factions. Each diagonal block is a Laplacian block with zero row sum and nonpositive off-diagonal entries. AI-Assistance Disclosure The authors used an artificial intelligence language model for rephrasing, language polishing, and basic grammatical correction of certain sentences. All mathematical results, algorithms, proofs, and scientific conclusions presented in this manuscript are entirely authored, verified, and approved”

PDF page 24

Classification

Rewriting existing author-written text

Multiplier

4

Verified

2026-08-23T19:04:42.417780Z

Structural counts