Counting five-node subgraphs
Résumé
We propose exact count formulae for the 21 topologically distinct non-induced connected subgraphs on five nodes,
in simple, unweighted and undirected graphs. We prove the main result using short and purely combinatorial
arguments that can be adapted to derive count formulae for larger subgraphs. To illustrate, we give analytic results
for some regular graphs, and present a short empirical application on real-world network data. We also discuss
the well-known result that induced subgraph counts follow as linear combinations of non-induced counts
Domaines
Sciences de l'Homme et Société
Origine : Fichiers produits par l'(les) auteur(s)