仅使用 n 和图密度估计图中 n 节点路径的数量
Estimate number of n-node paths in graph using only n and graph density
我有一个大而密集的图（约 33,000 个节点，约 3.45 亿条边，因此图密度约为 0.63）。我有兴趣估计此图中 3 边路径的数量。仅使用此信息（即没有邻接矩阵）是否有准确的估计？
如果粗略估计足够好（并且路径中的边数 k 是固定且小的）：设 d 为密度，那么您有 n 个起始节点，大约 n * d 个可能的第二个节点，。 .. 以及大约 n * d^k 个端节点。如果 k 较小，则与简单路径相比，具有循环的路径数量较少。所有路径的数量大约为 n^(k+1) * d^(k(k+1)/2) - 所以这将是一个（相当）粗略的估计。
我有一个大而密集的图（约 33,000 个节点，约 3.45 亿条边，因此图密度约为 0.63）。我有兴趣估计此图中 3 边路径的数量。仅使用此信息（即没有邻接矩阵）是否有准确的估计？
如果粗略估计足够好（并且路径中的边数 k 是固定且小的）：设 d 为密度，那么您有 n 个起始节点，大约 n * d 个可能的第二个节点，。 .. 以及大约 n * d^k 个端节点。如果 k 较小，则与简单路径相比，具有循环的路径数量较少。所有路径的数量大约为 n^(k+1) * d^(k(k+1)/2) - 所以这将是一个（相当）粗略的估计。