Overview

The Degree Centrality algorithm is used to find important nodes in the network, it measures the number of incoming and/or outgoing edges incident to the node, or the sum of weights of those edges. Degree is the simplest and most efficient graph algorithm since it only considers the 1-hop neighborhood of nodes. Degree plays a vital role in scientific computing, feature extraction, supernode recognition and other fields.

Concepts

In-Degree and Out-Degree

The number of incoming edges a node has is called its in-degree; accordingly, the number of outgoing edges is called out-degree. If ignores edge direction, it is degree.

In this graph, the red node has in-degree of 4 and out-degree of 3, and its degree is 7. Directed self-loop is regarded as an incoming edge and an outgoing edge.

Weighted Degree

In many applications, each edge of a graph has an associated numeric value, called weight. In weighted graph, weighted degree of a node is the sum of weights of all its neighbor edges. Unweighted degree is equivalent to when all edge weights are 1.

In this weighted graph, the red node has weighted in-degree of 0.5 + 0.3 + 2 + 1 = 3.8 and weighted out-degree of 1 + 0.2 + 2 = 3.2, and its weighted degree is 3.2 + 3.8 = 7.

Considerations

• Degree of isolated node only depends on its self-loop. If it has no self-loop, degree is 0.
• Every self-loop is counted as two edges attaching to its node. Directed self-loop is viewed as an incoming edge and an outgoing edge.

Parameters

Example Graph

To create this graph:

// Runs each row separately in order in an empty graphset
create().node_schema("user").edge_schema("follow")
create().edge_property(@follow, "score", float)
insert().into(@user).nodes([{_id:"Mike"},{_id:"Cathy"},{_id:"Anna"},{_id:"Joe"},{_id:"Sam"},{_id:"Bob"},{_id:"Bill"},{_id:"Tim"}])
insert().into(@follow).edges([{_from:"Mike", _to:"Cathy", score:1.9}, {_from:"Cathy", _to:"Mike", score:1.8}, {_from:"Mike", _to:"Anna", score:1.2},{_from:"Cathy", _to:"Anna", score:2.6},{_from:"Cathy", _to:"Joe", score:0.2},{_from:"Joe", _to:"Anna", score:4.2},{_from:"Bob", _to:"Joe", score:1.7},{_from:"Sam", _to:"Bob", score:3.5},{_from:"Sam", _to:"Anna", score:0.8},{_from:"Bill", _to:"Anna", score:2.3}])

Running on HDC Projections

Creating HDC Projections

To project the entire graph to the HDC server hdc-server-1 as hdc_degree:

hdc.graph.create("hdc_degree", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

File Writeback

algo(degree).params({
  project: "hdc_degree",
  return_id_uuid: "id",
  order: "desc"
}).write({
  file: {
    filename: "degree"
  }
})

Results:

_id,degree_centrality
Anna,5
Cathy,4
Joe,3
Mike,3
Bob,2
Sam,2
Bill,1
Tim,0

DB Writeback

Writes the degree_centrality values from the results to the specified node property. The property type is double.

algo(degree).params({
  project: "hdc_degree",
  edge_schema_property: 'score'
}).write({
  db:{ 
    property: 'degree'
  }
})

Full Return

exec{
  algo(degree).params({
    edge_schema_property: 'score',
    return_id_uuid: "id",
    order: 'desc'
  }) as r
  return r
} on hdc_degree

Results:

Stream Return

To find neighbors of the node with the highest out-degree:

exec{
  algo(degree).params({
    direction: "out",
    order: "desc",
    limit: 1 
  }).stream() as outTop1
  khop().src({_uuid == outTop1._uuid}).depth(1) as neigh
  return neigh._id
} on hdc_degree

Results:

Running on Distributed Projections

Creating Distributed Projections

To project the entire graph to its shard servers as dist_degree:

create().project("dist_degree", {
  nodes: {"*": ["*"]}, 
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true
})

File Writeback

algo(degree).params({
  project: "dist_degree",
  return_id_uuid: "id",
  order: "desc"
}).write({
  file: {
    filename: "degree"
  }
})

Results:

_id,degree_centrality
Anna,5
Cathy,4
Joe,3
Mike,3
Bob,2
Sam,2
Bill,1
Tim,0

DB Writeback

Writes the degree_centrality values from the results to the specified node property. The property type is double.

algo(degree).params({
  project: "dist_degree",
  edge_schema_property: 'score'
}).write({
  db:{ 
    property: 'degree'
  }
})