betweenness

Introduction

Betweenness is a kind of centrality measurement which is based on the shortest path between the vertices in a connected graph. As we know, for a connected graph, there exists at least one shortest path between every pair of vertices. The shortest path, for unweighted graphs, is the path passes through minimum number of edges. And for weighted graphs, it's the summation of weights on the path is minimized. By counting the number of these shortest paths that pass through the vertex, we can get the betweenness centrality. The Wikipedia page is here. (https://en.wikipedia.org/wiki/Betweenness_centrality )

Parameters

Parameter Name	Description	Comments
--input	Path to input data	Support HDFS.
--output	Path to output data	Output data contains two columns, namely node id and betweenness value.
--is_directed	Input network is directed or undirected	Default value is false, meaning undirected.
--chosen	vertex being observed	Default random select a vertex. Computation will be terminated based on the observation of this vertex shortest path count.
--max_iteration	max iteration.	For every iteration, random select a vertex and update the value of other vertices shortest path count.
--constant	computation termination constant.	Stop calculation if: shortest_path_count(chosen_vertex) > constant * |V|

Input Format

Input files should be formatted as follows:

<src>,<dst>,<weight>

where <src> and <dst> are integers of type uint32_t, representing the end nodes of an edge. <weight> is an optional input, indicating the weight of an edge. Note that Plato treats every input graph as undirected by default. For a directed graph, please ensure both <A, B> and <B, A> appear in the input file if they exist. Edges that appear more than once will be considered as multiple edges between the same pair of nodes.

Input example (Following numbers are synthetic and are for demonstration purpose only.)：

4564,823192,0.12
823192,973033,0.6
1713,823192,0.38

Output Format

Output files are formatted as follows：

<vertex_id>,<betweenness_value>

where <vertex_id> represents a node and < betweenness_value > gives the betweenness value of node.

Output example (Following numbers are synthetic and are for demonstration purpose only.)：

4564,0.2552393450530435
823192,0.5215760529282608

Source code

https://github.com/Tencent/plato/tree/master/plato/algo/bnc