Katz Centrality

Overview

Katz Centrality measures the influence of a node by considering not only its immediate connections but also its indirect connections at various distances while diminishing importance to more distant nodes.

Katz centrality values range from 0 to 1, with higher scores indicating nodes that exert greater influence over the flow and connectivity of the network.

References:

• L. Katz, A New Status Index Derived from Sociometric Analysis (1953)

Concepts

Katz Centrality

The Katz centrality is an extension of the eigenvector centrality. In the k-th round of influence propagation in eigenvector centrality, the centrality vector is simply updated as c(k) = Ac(k-1), where A is the adjacency matrix. Katz centrality modifies this computation by introducing two additional parameters, leading to the following update formula (which should be rescaled afterward):

where,

• α (alpha) is an attenuation factor that controls how influence decays during each propagation round. In the k-th round, the influences from indirect neighbors that are k steps away are considered, with their contributions cumulatively attenuated by a factor of αk. To ensure the convergence of c(k), α must be smaller than 1/λmax, where λmax is the dominant eigenvalue of the adjacency matrix A.
• β (beta) is a baseline centrality constant that ensures each node has a nonzero centrality score, even when it receives no influence. The common choice for β is 1.
• 1 is an n × 1 column vector of ones, where n is the number of nodes in the graph.

Example Graph

To create this graph:

// Runs each row separately in order in an empty graphset
create().node_schema("web").edge_schema("link")
create().edge_property(@link, "value", float)
insert().into(@web).nodes([{_id:"web1"}, {_id:"web2"}, {_id:"web3"}, {_id:"web4"}, {_id:"web5"}, {_id:"web6"}, {_id:"web7"}])
insert().into(@link).edges([{_from:"web1", _to:"web1",value:2}, {_from:"web1", _to:"web2",value:1}, {_from:"web2", _to:"web3",value:0.8}, {_from:"web3", _to:"web1",value:0.5}, {_from:"web3", _to:"web2",value:1.1}, {_from:"web3", _to:"web4",value:1.2}, {_from:"web3", _to:"web5",value:0.5}, {_from:"web5", _to:"web3",value:0.5}, {_from:"web6", _to:"web6",value:2}])

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as hdc_katz:

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

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

Parameters

Algorithm name: katz_centrality

File Writeback

CALL algo.katz_centrality.write("hdc_katz", {
  params: {
    return_id_uuid: "id",
    max_loop_num: 15,
    tolerance: 0.01,
    direction: "in"
  },
  return_params: {
    file: {
      filename: "katz_centrality"
    }
  }
})

algo(katz_centrality).params({
  projection: "hdc_katz",
  return_id_uuid: "id",
  max_loop_num: 15,
  tolerance: 0.01,
  direction: "in"
}).write({
  file: {
    filename: "katz_centrality"
  }
})

Result:

_id,katz_centrality
web3,0.399527
web7,0.335089
web1,0.40142
web5,0.368555
web6,0.365776
web2,0.401707
web4,0.368732

DB Writeback

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

CALL algo.katz_centrality.write("hdc_katz", {
  params: {
    edge_weight_property: "@link.value"
  },
  return_params: {
    db: {
      property: "kc"
    }
  }
})

algo(katz_centrality).params({
  projection: "hdc_katz",
  edge_weight_property: "@link.value"
}).write({
  db:{ 
    property: 'kc'
  }
})

Full Return

CALL algo.katz_centrality("hdc_katz", {
  params: {
    return_id_uuid: "id",    
    max_loop_num: 20,
    tolerance: 0.01,
    edge_weight_property: "value",
    direction: "in",
    alpha: 0.25,
    beta: 1,
    order: 'desc'
  },
  return_params: {}
}) YIELD kc
RETURN kc

exec{
  algo(katz_centrality).params({
    return_id_uuid: "id",    
    max_loop_num: 20,
    tolerance: 0.01,
    edge_weight_property: "value",
    direction: "in",
    alpha: 0.25,
    beta: 1,
    order: 'desc'
  }) as kc
  return kc
} on hdc_katz

Result:

Stream Return

CALL algo.katz_centrality("hdc_katz", {
  params: {
    edge_weight_property: "@link.value",
    direction: "in"
  },
  return_params: {
  	stream: {}
  }
}) YIELD kc
RETURN CASE
  WHEN kc.katz_centrality > 0.4 THEN "important"
  ELSE "normal"
  END as r, count(r) GROUP BY r

exec{
  algo(katz_centrality).params({
    edge_weight_property: "@link.value",
    direction: "in"
  }).stream() as kc
  with case
  when kc.katz_centrality > 0.4 then "important"
  else "normal"
  end as r
  group by r
  return r, count(r)
} on hdc_katz

Result: