Data Mining and Modelling for Biomedicine group, VIB Center for Inflammation Research, Ghent, Belgium.
Center for Medical Genetics, Ghent University Hospital, Ghent, Belgium.
PLoS One. 2018 Apr 26;13(4):e0195997. doi: 10.1371/journal.pone.0195997. eCollection 2018.
Graphlets are small network patterns that can be counted in order to characterise the structure of a network (topology). As part of a topology optimisation process, one could use graphlet counts to iteratively modify a network and keep track of the graphlet counts, in order to achieve certain topological properties. Up until now, however, graphlets were not suited as a metric for performing topology optimisation; when millions of minor changes are made to the network structure it becomes computationally intractable to recalculate all the graphlet counts for each of the edge modifications.
IncGraph is a method for calculating the differences in graphlet counts with respect to the network in its previous state, which is much more efficient than calculating the graphlet occurrences from scratch at every edge modification made. In comparison to static counting approaches, our findings show IncGraph reduces the execution time by several orders of magnitude. The usefulness of this approach was demonstrated by developing a graphlet-based metric to optimise gene regulatory networks. IncGraph is able to quickly quantify the topological impact of small changes to a network, which opens novel research opportunities to study changes in topologies in evolving or online networks, or develop graphlet-based criteria for topology optimisation.
IncGraph is freely available as an open-source R package on CRAN (incgraph). The development version is also available on GitHub (rcannood/incgraph).
图元是可以计数的小网络模式，用于描述网络的结构（拓扑结构）。作为拓扑优化过程的一部分，可以使用图元计数来迭代地修改网络并跟踪图元计数，以实现某些拓扑属性。然而，到目前为止，图元不适合作为执行拓扑优化的指标；当对网络结构进行数百万次的微小更改时，重新计算每个边缘修改的所有图元计数在计算上变得难以处理。
IncGraph 是一种计算相对于前一个状态的网络的图元计数差异的方法，与每次进行边缘修改时从头开始计算图元出现的情况相比，效率要高得多。与静态计数方法相比，我们的研究结果表明，IncGraph 将执行时间缩短了几个数量级。通过开发基于图元的指标来优化基因调控网络，证明了这种方法的有用性。IncGraph 能够快速量化网络小变化对拓扑结构的影响，这为研究进化或在线网络中拓扑结构的变化或开发基于图元的拓扑优化标准开辟了新的研究机会。
IncGraph 可在 CRAN（incgraph）上作为免费的开源 R 包使用。开发版本也可在 GitHub（rcannood/incgraph）上获得。
