Degree Distribution Algorithms

PGX 21.1.1 has two algorithms to compute the degree distribution. One for the out-degree and one for the in-degree distribution.

Out-Degree Distribution

Category structure evaluation

Algorithm ID pgx_builtin_s6_out_degree_distribution

Time Complexity O(V) with V = number of vertices

Space Requirement O(V) with V = number of vertices

Javadoc

• Analyst#outDegreeCentrality(PgxGraph graph)
• Analyst#outDegreeCentrality(PgxGraph graph, VertexProperty dc)

This version of the degree distribution will return a map with the distirbution of the out-degree (i.e. just outgoing edges) of the graph. For undirected graphs the algorithm will consider all the edges (incoming and outgoing) for the distribution.

Signature

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxMap;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

@GraphAlgorithm
public class OutdegreeDistribution {
  public void outdegreeDistribution(PgxGraph g, @Out PgxMap<Long, Long> distribution) {
    g.getVertices().forSequential(n -> {
      long degree = n.getOutDegree();

      distribution.increment(degree);
    });
  }
}

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure outdegree_distribution(graph G; map<int, long> distribution) {

  for (n: G.nodes) {
    int degree = n.outDegree();
    distribution[degree]++;
  }
}

In-Degree Distribution

Category structure evaluation

Algorithm ID pgx_builtin_s7_in_degree_distribution

Time Complexity O(V) with V = number of vertices

Space Requirement O(V) with V = number of vertices

Javadoc

• Analyst#inDegreeDistribution(PgxGraph graph)
• Analyst#inDegreeDistribution(PgxGraph graph, PgxMap distribution)

This version of the degree distribution will return a map with the distribution of the in-degree (i.e. just incoming edges) of the graph. For undirected graphs the algorithm will consider all the edges (incoming and outgoing) for the distribution.

Signature

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxMap;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

@GraphAlgorithm
public class IndegreeDistribution {
  public void indegreeDistribution(PgxGraph g, @Out PgxMap<Long, Long> distribution) {
    g.getVertices().forSequential(n -> {
      long degree = n.getInDegree();

      distribution.increment(degree);
    });
  }
}

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure indegree_distribution(graph G; map<int, long> distribution) {

  for (n: G.nodes) {
    int degree = n.inDegree();
    distribution[degree]++;
  }
}