Change Password

Input error
Input error
Input error
Submit
v2.x

Degree Centrality

Degree

  Basic  

Degree of a vertex (node) of a graph is the number of edges that are incident to the node, edge direction can be specified and weight factor of edge could be applied.

In Ultipa Graph, all per-node degree operations are conducted in a pure real-time fashion. Only whole-graph degree operations are invoked as tasks (asynchronously) due to computational complexity, especially on large graphs.

Note that in multigraphs, a loop (an edge whose starting node and ending node are identical) is counted as two edges

algo(degree)

Configuration items:

Item Data Type Specification Description
<ids> []int Node ID (Optional) To calculate for a group of nodes, or calculate for all nodes if not configured
<edge_schema_name> string Edge schema (Optional) The edge schema the property of which to be used as the weight factor, or use 1 as weight factor if not configured
(Need to be configured simultaneously with <edge_property_name>)
<edge_property_name> string Edge property (numeric type) (Optional) The edge property (must be LTE first) to be used as the weight factor, or use 1 as weight factor if not configured
(Need to be configured simultaneously with <edge_schema_name>)
<limit> int >0, -1 (Optional) The maximum number of results to return, or return all the results if not configured or configured to -1
<order> string 'ASC' or 'DESC' (Optional) To arrange the calculation results in ascending or descending order, or leave them un-ordered if not configured
<direction> string 'left' or 'right' (Optional) The direction of edges that contribute to the calculation, can be 'left' (in-pointing) or 'right' (out-pointing), or ignore edge direction if not configured

Validity of write_back():

Approach Destination
To database node property #degree_right, #degree_left, #degree_bidirection
To disk file /

Example: Calculate the out degree of node (_uuid = 1)

algo(degree).params({ ids: [1], direction: "right" })

Example: Calculate the degree of nodes (_uuid = 1,2,3), namely the sum of in degree and out degree

algo(degree).params({ ids: [1,2,3] })

Example: Calculate the whole-graph degree using edge property @card.level as weight factor, return 5 results

algo(degree).params({ edge_schema_name: "card", edge_property_name: "level", limit: 5 })

Example: Calculate the whole-graph in degree, arrange the results in descending order and return the top 3

algo(degree).params({ order: "DESC", direction: "left", limit: 3 })

Centrality

  Advanced  

algo(closeness_centrality)

Closeness centrality (or closeness) of a node is the reciprocal of sum of its distances (length of the shortest path) to all the other nodes within its connected component in the graphset. By this definition, the more central a node is in the graph, the closer it is to the other nodes, the samller the aforementioned sum of distances, and the bigger the reciprocal.

Closeness was first defined by American psychosociologist Alex Bavelas in 1950 as the reciprocal of the farness:

Obviously, the formula above would make the eventual C(x) too small to be meaningful, and with Ultipa graph it is normalized by multiplying k-1, which stands for the number of nodes excluding the subject node, and C(x) will always carry a value from 0 to 1:

Closeness centrality is a shortest-path-based algorithm that its computational complexity grows exponentially as the graphset gets larger. Ultipa Graph provides accurate closeness centrality calculation as well as approximate sampling calculation (for graphset with number of nodes beyond 10,000), with a sample number which is the base-10 logarithm of total number of nodes log(total_node_number). Fluctuation is observable in the approximate calculation result of a same subject node and will decrease as the graphset grows larger.

Configuration items:

Item Data Type Specification Description
<ids> []int Node ID (Optional) To calculate for a group of nodes, or calculate for all nodes if not configured
<limit> int >0, -1 (Optional) The maximum number of results to return, or return all the results if not configured or configured to -1
<direction> string 'left' or 'right' (Optional) The direction of edges that contribute to the calculation, can be 'left' (in-pointing) or 'right' (out-pointing), or ignore edge direction if not configured
<sample_size> string -1 or -2 (Optional) The accuracy of calculation, can be (-1) approximate calculation by sampling, or accurate calculation if not configured or configured to -2
<order> string 'ASC' or 'DESC' (Optional) To arrange the calculation results in ascending or descending order, or leave them un-ordered if not configured

Validity of write_back():

Approach Destination
To database node property #closeness_centrality_sample, #closeness_centrality_no_sample
To disk file /

Example: Calculate the closeness centrality of nodes (_uuid = 1,2,3,4)

algo(closeness_centrality).params({ ids: [1,2,3,4]})

Example: Calculate the whole-graph closeness centrality by sampling, with all the edges in right direction, return 10 result

algo(closeness_centrality).params({ limit: 10, direction: "right",sample_size: -1 })

algo(graph_centrality)

Graph centrality of a node is the reciprocal of its longest distance (length of the shortest-path) to all the other nodes within the connected component. It also produces a value between 0 and 1, and can be expressed as below:

In network analysis, graph centrality is used to identify the most important node in the graph, such as the most influential persons in a social network, the super-spreaders of CoVID-19, etc.

Configuration items:

Item Data Type Specification Description
<ids> []int Node ID (Optional) To calculate for a group of nodes, or calculate for all nodes if not configured
<limit> int >0, -1 (Optional) The maximum number of results to return, or return all the results if not configured or configured to -1
<order> string 'ASC' or 'DESC' (Optional) To arrange the calculation results in ascending or descending order, or leave them un-ordered if not configured

Validity of write_back():

Approach Destination
To database node property #graph_centrality
To disk file /

Example: Calculate graph centrality for all nodes

algo(graph_centrality).params({ limit: -1 })

algo(betweenness_centrality)

Betweenness centrality of a node represents how frequently the node appears in the shortest paths between each pair of other nodes in the graphset. Betweenness centrality of a node x is given by the below expression:

Where the denominator σ is the total number of shortest paths from node i to node j, and the numerator σ(x) is the number of those paths passing through node x. The summation of σ(x)/σ is normalized by dividing (k-1)(k-2)/2, which is the combination number of node pairs. Obviously, betweenness centrality is a value from 0 to 1.

Betweenness centrality finds wide applications in network theory, for instance, in a telco-network, a node with high(er) betweenness centrality would have more control over the network.

In highly connected graphs, betweenness centrality against the entire graph tends to consume lots of computational resources and is very time-consuming, especially on graphs larger than 100K nodes and edges. Ultipa Graph provides accurate betweenness centrality calculation as well as approximate sampling calculation (for graphset with number of nodes beyond 10,000), with a sample number which is the base-10 logarithm of total number of nodes log(total_node_number). Fluctuation is observable in the approximate calculation result of a same subject node and will decrease as the graphset grows larger.

Configuration item:

Item Data Type Specification Description
<ids> []int Node ID (Optional) To calculate for a group of nodes, or calculate for all nodes if not configured
<limit> int >0, -1 (Optional) The maximum number of results to return, or return all the results if not configured or configured to -1
<sample_size> string -1 or -2 (Optional) The accuracy of calculation, can be (-1) approximate calculation by sampling, or accurate calculation if not configured or configured to -2
<order> string 'ASC' or 'DESC' (Optional) To arrange the calculation results in ascending or descending order, or leave them un-ordered if not configured

Validity of write_back():

Approach Destination
To database node property #bc_sample, #bc_no_sample
To disk file /

Example: Calculate the accurate whole-graph betweenness centrality

algo(betweenness_centrality).params({ limit: 6, sample_size: -2 })