The distribution of minimum-weight cliques and other subgraphs in graphs with random edge weights

DOI10.1137/17M1138303MaRDI QIDQ4581213zbMATH OpenOpenAlexWikidataFDO

Authors Wesley Pegden, Gregory B. Sorkin, Alan Frieze

Publication date 15 August 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.04925

zbMATH Keywords

cliquesnetworksrandom graphsstatisticssubgraphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Approximations to statistical distributions (nonasymptotic) (62E17) Nonparametric hypothesis testing (62G10)

Abstract: We determine, asymptotically in $n$, the distribution and mean of the weight of a minimum-weight $k$-clique (or any strictly balanced graph $H$) in a complete graph $K_n$ whose edge weights are independent random values drawn from the uniform distribution or other continuous distributions. For the clique, we also provide explicit (non-asymptotic) bounds on the distribution's CDF in a form obtained directly from the Stein-Chen method, and in a looser but simpler form. The direct form extends to other subgraphs and other edge-weight distributions. We illustrate the clique results for various values of $k$ and $n$. The results may be applied to evaluate whether an observed minimum-weight copy of a graph $H$ in a network provides statistical evidence that the network's edge weights are not independently distributed but have some structure.

Recommendations

• The Min Mean-Weight Cycle in a Random Network
• Weights of cliques in a random graph model based on three-interactions
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• The effect of edge weights on clique weights
• On the value of a random minimum weight Steiner tree

Cites work

• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 775283 (Why is no real title available?)
• Threshold functions for small subgraphs
• Two moments suffice for Poisson approximations: The Chen-Stein method

Cited in

(3)

• Typical values of extremal-weight combinatorial structures with independent symmetric weights
• Successive shortest paths in complete graphs with random edge weights
• The effect of edge weights on clique weights

This page was built for publication: The distribution of minimum-weight cliques and other subgraphs in graphs with random edge weights

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4581213)