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

Run the following statements on an empty graph to define its structure and insert data:

GQLUQL
ALTER GRAPH CURRENT_GRAPH ADD NODE {
  web ()
};
ALTER GRAPH CURRENT_GRAPH ADD EDGE {
  link ()-[{value float}]->()
};
INSERT (web1:web {_id: "web1"}),
       (web2:web {_id: "web2"}),
       (web3:web {_id: "web3"}),
       (web4:web {_id: "web4"}),
       (web5:web {_id: "web5"}),
       (web6:web {_id: "web6"}),
       (web7:web {_id: "web7"}),
       (web1)-[:link {value: 2}]->(web1),
       (web1)-[:link {value: 1}]->(web2),
       (web2)-[:link {value: 0.8}]->(web3),
       (web3)-[:link {value: 0.5}]->(web1),
       (web3)-[:link {value: 1.1}]->(web2),
       (web3)-[:link {value: 1.2}]->(web4),
       (web3)-[:link {value: 0.5}]->(web5),
       (web5)-[:link {value: 0.5}]->(web3),
       (web6)-[:link {value: 2}]->(web6);

Creating HDC Graph

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

GQLUQL
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static"
}

Parameters

Algorithm name: katz_centrality

File Writeback

UQL
algo(katz_centrality).params({
  projection: "my_hdc_graph",
  return_id_uuid: "id",
  max_loop_num: 50,
  tolerance: 0.00001,
  direction: "in",
  alpha: 0.4
}).write({
  file: {
    filename: "katz_centrality"
  }
})

Result:

File: katz_centrality
_id,katz_centrality
web3,0.458447
web7,0.127183
web1,0.517601
web5,0.310561
web6,0.211972
web2,0.517601
web4,0.310561

DB Writeback

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

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

Full Return

UQL
exec{
  algo(katz_centrality).params({
    return_id_uuid: "id",    
    max_loop_num: 100,
    tolerance: 0.00001,
    edge_weight_property: "value",
    direction: "in",
    alpha: 0.4,
    beta: 1,
    order: "desc"
  }) as kc
  return kc
} on my_hdc_graph

Result:

Stream Return

UQL
exec{
  algo(katz_centrality).params({
    return_id_uuid: "id",    
    max_loop_num: 100,
    tolerance: 0.00001,
    edge_weight_property: "value",
    direction: "in",
    alpha: 0.4,
    beta: 1,
    order: "desc"
  }).stream() as kc
  return kc
} on my_hdc_graph

Result: