如何验证图表是否服从权力法则？ [英] How to verify if a graph obeys a power law?

问题描述

我使用GraphStream生成syntethic图。
验证图表是否服从幂律的公式是什么？
（我只有节点和边的数目）
谢谢。

解决方案

带有名为关系的边集合的图。
我们可以使用ArangoDB中的AQL在此边缘集合上使用全表扫描来收集所需的数据。
我们需要统一_from和_to，以便我们可以对它们进行计数。
我们使用collect语句评估每个顶点的直径：

  FOR oneEdge IN关系
 FOR edgeLink IN [oneEdge._from，oneEdge._to] 
 COLLECT edgesCounterItem = edgeLink WITH COUNT INTO graphDiameter 
 RETURN {what：edgesCounterItem，count：graphDiameter} 
  

现在我们知道直径了，我们需要再一次用直径分组：

 对于oneEdge IN关系
 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} 
  

现在我们想要这个很好的排序所以我们可以很容易地绘制它：

 对于oneEdge IN关系
对于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} 
  

通过这张图表，您可以确定 $ b

$ b

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.

解决方案

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屋！