Node distribution

This module collects some metrics on the distribution of nodes.

Methods

distribution.center_of_mass(g: Graph, pos: str | dict | None = None, weight: str | dict | None = None) → Vector | None

Calculates the center of mass of all vertices (i.e. the average vertex position). Edges are not considered.

Parameters:

• g (nx.Graph) – A networkX graph

• pos (Union[str, dic, None]) – Optional node position dictionary. If not supplied, node positions are read from the graph directly. If given as a string, the property under the given name in the networkX graph is used.

• weight (Union[str, dict, None]) – An optional weight dictionary. If given as a string, the property under the given name in the networkX graph is used.

Returns:

A vector representing the position of the center of mass. If the graph is empty, None is returned.

Return type:

Optional[Vector]

distribution.closest_pair_of_elements(g: Graph, pos: str | dict | None = None, consider_crossings=False)

Returns the two graph elements (i.e. nodes and edges) with minimum distance between between them.

Parameters:

• g (nx.Graph) – A networkX graph

• pos (Union[str, dic, None]) – Optional node position dictionary. If not supplied, node positions are read from the graph directly. If given as a string, the property under the given name in the networkX graph is used.

• consider_crossings – Whether or not to consider crossings as well. If a crossing exists, the closest pair of elements consists of two crossing edges.

Returns:

The keys of the two closest graph elements as well as their distance

Return type:

(object, object, float)

distribution.closest_pair_of_points(g: Graph, pos: str | dict | None = None)

Returns the two closest points a, b together with their euclidean distance in the form (a,b, distance)

Parameters:

• g (nx.Graph) – A networkX graph

• pos (Union[str, dic, None]) – Optional node position dictionary. If not supplied, node positions are read from the graph directly. If given as a string, the property under the given name in the networkX graph is used.

Returns:

The keys of the two involved nodes as well as their distance

Return type:

(object, object, float)

distribution.concentration(g: Graph, pos: str | dict | None = None, grid_size: int | float = 0, bounding_box: Tuple[int | float, int | float, int | float, int | float] = None) → float

Calculates the concentration of the given networkX graph g. The concentration is a density measure counting the number of nodes in each cell of a sqrt(n) * sqrt(n) grid, where n is the number of nodes in the graph. The counts for each cell are then summed up and divided by n-1.

A concentration of 1 means that all nodes are within a single grid cell, and a concentration of 0 means that all nodes are evenly spaced between the cells.

The measure was first defined by Taylor and Rodgers[1].

Parameters:

• g (nx.Graph) – A networkX graph

• pos (Union[str, dic, None]) – Optional node position dictionary. If not supplied, node positions are read from the graph directly. If given as a string, the property under the given name in the networkX graph is used.

• grid_size (numeric) – For large graphs, where the calculation might be time sensitive, set a bigger grid size to improve performance. A higher grid size reduces the precision of the metric. In most cases, leaving the default value should be sufficient.

• bounding_box (Tuple[numeric, numeric, numeric, numeric]) – The bounding box in the form of (x_min, y_min, x_max, y_max) of the graph. If not specified, a tight bounding box is used. All nodes must be contained within the bounding box.

Returns:

The concentration of the graph between 0 and 1

Return type:

float

distribution.gabriel_ratio(g: Graph, pos: str | dict | None = None) → float

The Gabriel ratio is the ratio of all number of nodes falling within a minimum circle covering an edge for any edge.

This measure was first defined by Mooney et al.[2].

Parameters:

• g (nx.Graph) – A networkX graph

• pos (Union[str, dic, None]) – Optional node position dictionary. If not supplied, node positions are read from the graph directly. If given as a string, the property under the given name in the networkX graph is used.

Returns:

The Gabriel ratio between 0 and 1

Return type:

float

distribution.heatmap(g: Graph, pos: dict | list, values: list | None, grid_size: int, bounding_box: Tuple[int | float, int | float, int | float, int | float] = None, average: bool = True) → ndarray

Calculates a heatmap for all the values in values at the positions pos. The values and positions are expected to be of the same length and in the same order.

Parameters:

• g (nx.Graph) – A networkX graph

• pos (pos: Optional[dict, list]) – A dictionary or list of tuples of x and y positions

• values (Optional[list, None]) – A list of values. If None, 1 is assumed for each position.

• grid_size (int) – Number of grid cells per dimension. A grid size of 5 would lead to 5x5 = 25 individual cells.

• bounding_box (Tuple[numeric, numeric, numeric, numeric]) – The bounding box of the heatmap. If None, the minimum sized bounding box containing the whole graph is assumed.

• average (bool) – If true, each the sum of each cell is divided by the number of values falling into it.

Returns:

A two dimensional array with all grid cell values.

Return type:

np.ndarray

distribution.homogeneity(g: Graph, pos: str | dict | None = None) → float

Calculates how evenly the nodes are distributed among the four quadrants.

The measure was first defined by Taylor and Rodgers[1].

Parameters:

• g (nx.Graph) – A networkX graph

• pos (Union[str, dic, None]) – Optional node position dictionary. If not supplied, node positions are read from the graph directly. If given as a string, the property under the given name in the networkX graph is used.

Returns:

A value between 0 and 1. A value of 0 indicates an even distribution among the quadrants, and 1 the worst case distribution.

Return type:

float

distribution.horizontal_balance(g: Graph, pos: str | dict | None = None, use_relative_coordinates: bool = True) → float

Returns a value between -1 and 1 indicating the horizontal balance.

A value of 0 means a perfectly even balance between the upper and lower half. A value of -1 means that all nodes lie on the lower half, a value of 1 means that all nodes lie on the upper half.

Parameters:

• g (nx.Graph) – A networkX graph

• pos (Union[str, dic, None]) – Optional node position dictionary. If not supplied, node positions are read from the graph directly. If given as a string, the property under the given name in the networkX graph is used.

• use_relative_coordinates (bool) – Indicates whether to use the absolute zero points or relative coordinates. If use_relative_coordinates is true, the horizontal split line will be at the center between the lowest and the highest node in the graph. If use_relative_coordinates is false, the horizontal split line is put at y=0.

Returns:

A value between -1 and 1.

Return type:

float

distribution.node_orthogonality(g: Graph, pos: dict | list | None = None, width: int = None, height: int = None) → float

Calculates the node orthogonality of a graph, defined by how densely packed nodes are on the grid. More precisely, the metric is defined by the number of nodes devided by the number of grid cells.

Parameters:

• g (nx.Graph) – A networkX graph

• pos (Union[str, dic, None]) – Optional node position dictionary. If not supplied, node positions are read from the graph directly. If given as a string, the property under the given name in the networkX graph is used.

• width (int) – Total number of horizontal grid cells. If not supplied, a minimal integer grid fitting g is assumed.

• height (int) – Total number of vertical grid cells. If not supplied, a minimal integer grid fitting g is assumed.

Returns:

A metric of node orthogonality between 0 and 1

Return type:

float

distribution.smallest_enclosing_circle(g: Graph, pos: str | dict | None = None) → Tuple[Vector, float]

Implementation of Welzl’s algorithm to find the smallest enclosing circle of a graph.

Parameters:

• g (nx.Graph) – A networkX graph

• pos (Union[str, dic, None]) – Optional node position dictionary. If not supplied, node positions are read from the graph directly. If given as a string, the property under the given name in the networkX graph is used.

Returns:

The centre and radius of the smallest circle containing all nodes in g.

Return type:

gdMetriX.Circle

distribution.smallest_enclosing_circle_from_point_set(points: Iterable) → Tuple[Vector, float]

Implementation of Welzl’s algorithm to find the smallest enclosing circle of a point set.

Parameters:

points – List of points

Returns:

The centre and radius of the smallest circle containing all points in the list.

Return type:

gdMetriX.Circle

distribution.vertical_balance(g: Graph, pos: str | dict | None = None, use_relative_coordinates: bool = True) → float

Returns a value between -1 and 1 indicating the vertical balance.

A value of 0 means a perfectly even balance between the left and right half. A value of -1 means that all nodes lie on the left half, a value of 1 means that all nodes lie on the right half.

Parameters:

• g (nx.Graph) – A networkX graph

• pos (Union[str, dic, None]) – Optional node position dictionary. If not supplied, node positions are read from the graph directly. If given as a string, the property under the given name in the networkX graph is used.

• use_relative_coordinates (bool) – Indicates whether to use the absolute zero points or relative coordinates. If use_relative_coordinates is true, the vertical split line will be at the center between the leftmost and the rightmost node in the graph. If use_relative_coordinates is false, the vertical split line is put at x=0.

Returns:

A value between -1 and 1.

Return type:

float

Bibliography

[1] (1,2)

M. Taylor and P. Rodgers. Applying graphical design techniques to graph visualisation. In Ninth International Conference on Information Visualisation (IV’05), 651–656. IEEE, 2005. doi:10.1109/IV.2005.19.

[2]

Gavin J. Mooney, Helen C. Purchase, Michael Wybrow, and Stephen G. Kobourov. The multi-dimensional landscape of graph drawing metrics. In 17th IEEE Pacific Visualization Symposium. Pacific Visualization 2024, 2024.