Parameterized clique on inhomogeneous random graphs
Parameterized clique on inhomogeneous random graphs
复制标题
非齐次随机图上的参数化团
DOI：
10.1016/j.dam.2014.10.018
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
A. Krohmer
中科院分区：
文献类型：
--
作者：
T. Friedrich;A. Krohmer
在图中求团是一个典型的np困难和参数化难解问题。然而，在社交网络或生物网络等典型应用中，所考虑的图是无标度的，即它们的度序列遵循幂律。它们的特定结构可以通过算法加以利用，从而可以更有效地解决派系问题。证明了在具有n个节点和幂律指数β的非齐次随机图上，当β≥3时，在O (n)时间内可以找到大小为k的团，当2< β< 3时，在O （n e k 4）时间内可以找到大小为k的团。
Finding cliques in graphs is a classical problem which is in general NP-hard and parameterized intractable. In typical applications like social networks or biological networks, however, the considered graphs are scale-free, ie, 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 O (n) for β≥ 3 and in time O (n e k 4) for 2< β< 3.
登录
查看更多内容
求解稀疏图中的最大团：$$O(nm n2^{d/4})$$O(nm n2d/4) 算法用于 $$d$$d 简并图
影响因子：
1.6
作者：
Austin Buchanan;J. Walteros;S. Butenko;P. Pardalos
通讯作者：
P. Pardalos
DOI：
10.1137/0215020
发表时间：
1986-02
期刊：
SIAM J. Comput.
影响因子：
--
作者：
L. Levin
通讯作者：
L. Levin
无标度网络上的参数化团
DOI：
--
发表时间：
2012
期刊：
International Symposium on Algorithms and Computation
影响因子：
--
作者：
T. Friedrich;Anton Krohmer
通讯作者：
Anton Krohmer
随机无标度网络集合中的派系数量
DOI：
10.1016/j.physd.2006.09.013
发表时间：
2006
期刊：
Physica D: Nonlinear Phenomena
影响因子：
--
作者：
G. Bianconi;M. Marsili
通讯作者：
M. Marsili
具有给定预期度数的网络的高效生成
影响因子：
1
作者：
Joel C. Miller;A. Hagberg
通讯作者：
A. Hagberg