图 书 馆
网络逼近图案数Approximating the Number of Network Motifs |
|
| 课程网址: | http://videolectures.net/waw09_gonen_annm/ |
| 主讲教师: | Mira Gonen, Yuval Shavitt |
| 开课单位: | 特拉维夫大学 |
| 开课时间: | 2009-03-12 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | World Wide Web, the Internet, coupled biological and chemical systems, neural networks, and social interacting species, are only a few examples of systems composed by a large number of highly interconnected dynamical units. These networks contain characteristic patterns, termed network motifs, which occur far more often than in randomized networks with the same degree sequence. Several algorithms have been suggested for counting or detecting the number of induced or non-induced occurrences of network motifs in the form of trees and bounded treewidth subgraphs of size O(log(n)), and of size at most 7 for some motifs. In addition, counting the number of motifs a node is part of was recently suggested as a method to classify nodes in the network. The promise is that the distribution of motifs a node participate in is an indication of its function in the network. Therefore, counting the number of network motifs a node is part of provides a major challenge. However, no such practical algorithm exists. We present several algorithms with time complexity O((e^2k) * k * n * |E| * log((1/delta)/epsilon^2)) that, for the first time, approximate for every vertex the number of non-induced occurrences of the motif the vertex is part of, for k-length cycles, k-length cycles with a chord, and (k − 1)-length paths, where k = O(log(n)), and for all motifs of size of at most four. In addition, we show algorithms that approximate the total number of non-induced occurrences of these network motifs, when no efficient algorithm exists. Some of our algorithms use the color coding technique. |
| 关 键 词: | 网络; 基序; 图案 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2020-06-12：邬启凡(课程编辑志愿者) |
| 阅读次数: | 66 |