Algorithmic Tools for Understanding the Motif Structure of Networks
Algorithmic Tools for Understanding the Motif Structure of Networks
复制标题
DOI：
10.1007/978-3-031-26390-3_1
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Tianyi Chen;Brian Matejek;M. Mitzenmacher;Charalampos E. Tsourakakis
中科院分区：
文献类型：
--
作者：
Tianyi Chen;Brian Matejek;M. Mitzenmacher;Charalampos E. Tsourakakis
模体是小型子图模式，对理解生物和社交网络的结构和功能起着关键作用。目前评估一个基序的统计意义的方法依赖于计算它在整个网络中的出现次数，并将该计数与它在某个空生成模型下的预期计数进行比较。这种方法可能是误导，由于组合文物。也就是说，可能会有一个大的计数为一个motif由于多个副本共享许多顶点和边连接到一个子图，如团，完成了多个副本的motif.在这项工作中，我们引入了一个新的概念（f，q）-跨越motif。一个模体是（f，q）-跨越的，如果存在q-分数的节点诱导出an f-分数的G的出现。直觉上，当f接近于1，q接近于0时，大多数的出现都局限于一个小的节点集合中，因此它的统计显著性很可能是由于组合伪影。我们提出了有效的算法来找到一个给定的最大值f和一个给定的最小值f，其中一个基序是（f，q）-跨越，并在现实世界的数据集上评估它们。我们的方法成功地识别组合文物，否则去未被检测到使用标准的方法进行评估统计significant.Finally，我们利用网络的主题结构designMotifScope，一个算法，作为输入的一个图和两个主题，并找到子图的图，其中出现频率和频繁分别。我们表明，一个好的选择允许我们在大型网络中发现异常，包括社交图中的二分派系，以及比特币市场中不信任的子图。
Motifs are small subgraph patterns that play a key role towards understanding the structure and the function of biological and social networks. The currentde factoapproach towards assessing the statistical significance of a motifrelies on counting its occurrences across the network, and comparing that count to its expected count under some null generative model. This approach can be misleading due tocombinatorial artifacts. That is, there may be a large count for a motif due to multiple copies sharing many vertices and edges connected to a subgraph, such as a clique, that completes the multiple copies of the motif.In this work we introduce the novel concept of an (f,q)-spanning motif. A motifis (f,q)-spanning if there exists aq-fraction of the nodes that induces anf-fraction of the occurrences ofinG. Intuitively, whenfis close to 1, andqclose to 0, most of the occurrences ofare localized in a small set of nodes, and thus its statistical significance is likely to be due to a combinatorial artifact. We propose efficient heuristics for finding the maximumffor a givenqand minimumqfor a givenffor which a motif is (f,q)-spanning and evaluate them on real-world datasets. Our methods successfully identify combinatorial artifacts that otherwise go undetected using the standard approach for assessing statistical significance.Finally, we leverage the motif structure of a network to designMotifScope, an algorithm that takes as input a graph and two motifs, and finds subgraphs of the graph whereoccur infrequently and frequently respectively. We show that a good selection ofallows us to find anomalies in large networks, including bipartite cliques in social graphs, and subgraphs rated with distrust in Bitcoin markets.