Parameterized Clique on Scale-Free Networks
Parameterized Clique on Scale-Free Networks
复制标题
无标度网络上的参数化团
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Anton Krohmer
中科院分区：
文献类型：
--
作者：
T. Friedrich;Anton Krohmer
在图中查找派系是一个经典问题，通常是 NP 困难且参数化的棘手问题。然而，在社交网络或蛋白质-蛋白质相互作用网络等典型应用中，所考虑的图是无标度的，即它们的度数序列遵循幂律。它们的特定结构可以通过算法加以利用，从而可以更有效地解决派系问题。我们证明，在具有 n 个节点和幂律指数 γ 的非齐次随机图上，对于 γ ≥ 3，可以在时间 \(\mathcal{O}(n^2)\) 中找到大小为 k 的团；对于 2 < γ < 3，可以在时间 \(\mathcal{O}(n\, \exp(k^4))\) 中找到大小为 k 的团。
Finding cliques in graphs is a classical problem which is in general NP-hard and parameterized intractable. However, in typical applications like social networks or protein-protein interaction networks, the considered graphs are scale-free, i.e., their degree sequence follows a power law. Their specific structure can be algorithmically exploited and makes it possible to solve clique much more efficiently. We prove that on inhomogeneous random graphs with n nodes and power law exponent γ, cliques of size k can be found in time \(\mathcal{O}(n^2)\) for γ ≥ 3 and in time \(\mathcal{O}(n\, \exp(k^4))\) for 2 < γ < 3.