Incremental Maintenance of Maximal Bicliques in a Dynamic Bipartite Graph
Incremental Maintenance of Maximal Bicliques in a Dynamic Bipartite Graph
复制标题
DOI：
10.1109/tmscs.2018.2802920
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
A. Das;Srikanta Tirthapura
中科院分区：
文献类型：
--
作者：
A. Das;Srikanta Tirthapura
我们考虑增量维护的最大bicliques从一个动态的二分图，随着时间的推移，由于增加的边缘变化。当新的边缘被添加到图中，我们试图枚举的最大bicliques的集合中的变化，而不枚举的最大bicliques的集合，保持不受影响。在一个有效的算法的挑战是枚举的变化，而不显式枚举的所有最大biclique的集合。在这项工作中，我们提出了（1）近紧界的变化幅度在一个图的最大biclies的集合，由于边集的变化，和（2）增量算法枚举的变化在一组最大biclies。对于向图中添加恒定数量的边的情况，我们的算法是“变化敏感的”，即，它的时间复杂度与最大双列集的变化幅度成比例。据我们所知，这是第一个增量算法枚举最大bicliques在动态图中，具有可证明的性能保证。我们的算法易于实现，实验结果表明其性能比基线实现高出几个数量级。
We consider incremental maintenance of maximal bicliques from a dynamic bipartite graph that changes over time due to the addition of edges. When new edges are added to the graph, we seek to enumerate the change in the set of maximal bicliques, without enumerating the set of maximal bicliques that remain unaffected. The challenge in an efficient algorithm is to enumerate the change without explicitly enumerating the set of all maximal bicliques. In this work, we present (1) Near-tight bounds on the magnitude of change in the set of maximal bicliques of a graph, due to a change in the edge set, and an (2) Incremental algorithm for enumerating the change in the set of maximal bicliques. For the case when a constant number of edges are added to the graph, our algorithm is “change-sensitive”, i.e., its time complexity is proportional to the magnitude of change in the set of maximal bicliques. To our knowledge, this is the first incremental algorithm for enumerating maximal bicliques in a dynamic graph, with a provable performance guarantee. Our algorithm is easy to implement, and experimental results show that its performance exceeds that of baseline implementations by orders of magnitude.