如何验证图形是否遵守幂律? [英] How to verify if a graph obeys a power law?

问题描述

我正在使用 GraphStream 生成合成图.验证图形是否服从幂律的公式是什么?(我只有节点和边的数量)谢谢.

I am using the GraphStream to generate syntethic graphs. What is the formula to verify if the graph obeys the power law? (I have only the number of nodes and edges) Thanks.

推荐答案

所以我们有一个带有名为 relations 的边集合的图.我们可以使用 ArangoDB 中的 AQL 在这个边缘集合上使用全表扫描来收集所需的数据.我们需要统一 _from 和 _to 以便我们可以计算它们.我们使用 collect 语句来评估每个顶点的直径:

So we have a graph with an edge collection named relations. We can gather the required data using a full table scan on this edge collection using AQL in ArangoDB. We need to unify _from and _to so we can count them. We use the collect statement to evaluate the diameter for each vertex:

FOR oneEdge IN relations 
  FOR edgeLink IN [ oneEdge._from, oneEdge._to ]
    COLLECT edgesCounterItem = edgeLink WITH COUNT INTO graphDiameter
      RETURN { what: edgesCounterItem, count: graphDiameter }

既然我们知道了直径，我们需要再次按直径分组:

Now that we know the diameters, we need to group once more by the diameters:

FOR oneEdge IN relations 
  FOR edgeLink IN [ oneEdge._from, oneEdge._to ]
    COLLECT edgesCounterItem = edgeLink WITH COUNT INTO graphDiameter
      COLLECT powerCounts = graphDiameter WITH COUNT INTO powerCounter
        RETURN {numberEdges: powerCounts, vertexCount: powerCounter}

现在我们想要很好地排序，以便我们可以轻松地绘制它:

Now we want this nicely sorted so we can easily plot it:

FOR oneEdge IN relations 
  FOR edgeLink IN [ oneEdge._from, oneEdge._to ]
    COLLECT edgesCounterItem = edgeLink WITH COUNT INTO graphDiameter
      COLLECT powerCounts = graphDiameter WITH COUNT INTO powerCounter
        SORT powerCounts
          RETURN {numberEdges: powerCounts, vertexCount: powerCounter}

通过此图表，您将能够确定幂律是否满足.

With this chart you then will be able to determine whether a power law is fullfilled or not.

注意:这肯定需要大量的系统资源来计算.

Note: this definitely will require a lot of system resources to compute.

这篇关于如何验证图形是否遵守幂律?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！