论文标题
计算五节点子图
Counting five-node subgraphs
论文作者
论文摘要
我们在简单，未加权和未方向的五个节点上提出了21个拓扑不同的非诱导连接子图的确切计数公式。我们使用简短和纯粹的组合参数证明了主要结果，该参数可以适应用于较大子图的计数公式。为了说明，我们给出一些常规图表的分析结果，并在现实世界网络数据上提供了简短的经验应用。我们还讨论了众所周知的结果，即诱导的子图计数随着非诱导计数的线性组合而言。
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.
