论文标题
连接较低的6个单位的快速计数方法
A Fast Counting Method for 6-motifs with Low Connectivity
论文作者
论文摘要
A $ K $ -MOTIF（或Graphlet）是图或网络中$ K $节点的子图。在复杂网络中的图案计数是对社交网络和生物信息学研究引起的各种真实图表的网络分析的一个充分研究的问题。特别是，由于其在理解社交网络的行为方面的意义，三角计数问题受到了很多关注。同样，最近有3个节点的子图最近受到了很多关注。尽管已经在此问题上开发了成功的方法，但大多数现有算法都无法扩展到具有数百万节点和边缘的大型网络。 本文的主要贡献是一项初步研究，该研究将Pinar，Seshadhri和Vishal提供的确切计数算法纳入了6-motifs的集合。该方法使用尺寸较小的基序的计数来获得较低的换连性的6-motifs的计数，即包含切割的vertex或剪切边缘。因此，它规避了在大型网络中计数子图时自然产生的组合爆炸。
A $k$-motif (or graphlet) is a subgraph on $k$ nodes in a graph or network. Counting of motifs in complex networks has been a well-studied problem in network analysis of various real-word graphs arising from the study of social networks and bioinformatics. In particular, the triangle counting problem has received much attention due to its significance in understanding the behavior of social networks. Similarly, subgraphs with more than 3 nodes have received much attention recently. While there have been successful methods developed on this problem, most of the existing algorithms are not scalable to large networks with millions of nodes and edges. The main contribution of this paper is a preliminary study that genaralizes the exact counting algorithm provided by Pinar, Seshadhri and Vishal to a collection of 6-motifs. This method uses the counts of motifs with smaller size to obtain the counts of 6-motifs with low connecivity, that is, containing a cut-vertex or a cut-edge. Therefore, it circumvents the combinatorial explosion that naturally arises when counting subgraphs in large networks.
