A combinatorial approach to graphlet counting
A combinatorial approach to graphlet counting
复制标题
DOI：
10.1093/bioinformatics/btt717
复制
发表时间：
2014-02-15
期刊：
影响因子：
5.8
通讯作者：
Demsar, Janez
中科院分区：
文献类型：
--
作者：
Hocevar, Tomaz;Demsar, Janez
动机：称为Graphlet的小诱导子图正在出现，作为探索网络的全局和局部结构以及分析单个节点的角色的可能工具。其发现和计数算法的计算复杂性是阻碍其广泛应用的障碍之一。结果：我们提出了一种新的组合方法来计算网络节点的图块和轨道签名。该算法建立了一个方程式系统，将来自最多五个节点的图形的轨道计数联系起来，允许通过仅枚举一个节点来计算所有轨道计数。与现有的纯枚举算法相比，该算法在稀疏图中的实际时间复杂度降低了一个数量级。
Motivation: Small-induced subgraphs called graphlets are emerging as a possible tool for exploration of global and local structure of networks and for analysis of roles of individual nodes. One of the obstacles to their wider use is the computational complexity of algorithms for their discovery and counting.Results: We propose a new combinatorial method for counting graphlets and orbit signatures of network nodes. The algorithm builds a system of equations that connect counts of orbits from graphlets with up to five nodes, which allows to compute all orbit counts by enumerating just a single one. This reduces its practical time complexity in sparse graphs by an order of magnitude as compared with the existing pure enumeration-based algorithms.