bluegraph.core.analyse package

Reference page for the bluegraph.core.analyse package.

Graph metrics

class bluegraph.core.analyse.metrics.MetricProcessor

Abstract class for processing various graph metrics.

exception MetricProcessingException

exception MetricProcessingWarning

abstract betweenness_centrality(distance=None, write=False)

Compute (weighted) betweenness centrality.

abstract closeness_centrality(distance, write=False)

Compute (weighted) closeness centrality.

abstract degree_centrality(weight=None, write=False)

Compute (weighted) degree centrality.

classmethod from_graph_object(graph_object)

Instantiate a MetricProcessor directly from a Graph object.

abstract get_pgframe()

Get a new pgframe object from the wrapped graph object.

abstract pagerank_centrality(weight=None, write=False)

Compute (weighted) PageRank centrality.

Path search

class bluegraph.core.analyse.paths.PathFinder

Abstract class for a path finder.

exception NoPathException

Exception class for ‘path does not exist.

exception NotImplementedError

Exception class for not implemented bits.

exception PathSearchException

Exception class for generic path search error.

all_shortest_paths(source, target, exclude_edge=False)

Compute all shortest paths from the source to the target.

This function computes all the shortest (unweighted) paths from the source to the target.

Parameters:

• source (str) – Source node ID

• target (str) – Target node ID

• exclude_edge (bool, optional) – Flag indicating whether the direct edge from the source to the target should be excluded from the result (if exists).

abstract get_distance(source, target, distance)

Get distance value between source and target.

abstract get_subgraph_from_paths(paths)

Get a subgraph given the input paths.

abstract minimum_spanning_tree(distance, write=False, write_property=None)

Compute the minimum spanning tree.

Parameters:

• distance (str) – Distance to minimize when computing the minimum spanning tree (MST)

• write (bool, optional) – Flag indicating whether the MST should be returned as a new graph object or saved within a Boolean edge property being True whenever a given edge belongs to the MST.

• write_property (str, optional) – Edge property name for marking edges beloning to the MST.

Returns:

tree – The minimum spanning tree graph object

Return type:

graph object

n_nested_shortest_paths(source, target, top_level_n, nested_n=None, depth=1, distance=None, strategy='naive', exclude_edge=False)

Find top n nested paths. Nested paths are found iteratively for each level of depth. For example, if e1 <-> e2 <-> … <-> eN is a path on the current level of depth, then the function searches for paths between each consecutive pair of nodes (e1 and e2, e2 and e3, etc.). :param graph: Input graph object :type graph: nx.Graph :param source: Source node ID :type source: str :param target: Target node ID :type target: str :param top_level_n: Number of top paths to include in the result :type top_level_n: int :param nested_n: Number of top paths to include in the result for the depth > 1 :type nested_n: int :param depth: Number of interactions of the path search :type depth: int, optional :param distance: The name of the attribute to use as the edge distance :type distance: str, optional :param strategy: Path finding strategy: naive or yen. By default, naive. :type strategy: str, optional

Returns:

current_paths – List containing best nested paths according to the distance score

Return type:

list

n_shortest_paths(source, target, n, distance=None, strategy='naive', exclude_edge=False)

Compute n shortest paths from the source to the target.

Two search strategies are available: ‘naive’ and ‘yen’. The naive strategy first finds the set of all shortest paths from the source to the target node, it then ranks them by the cumulative distance score and returns n best paths. The second strategy uses Yen’s algorithm [1] for finding n shortest paths. The first naive strategy performs better for highly dense graphs (where every node is connected to almost every other node). Note that if there are less than n unweighted shortest paths in the graph, the naive strategy may return less than n paths.

1. Yen, Jin Y. “Finding the k shortest loopless paths in a network”. Management Science 17.11 (1971): 712-716.

Parameters:

• source (str) – Source node ID

• target (str) – Target node ID

• n (int) – Number of top paths to include in the result

• distance (str, optional) – The name of the attribute to use as the edge distance

• path_condition (func, optional) – Edge filtering function returning Boolean flag

• strategy (str, optional) – Path finding strategy: naive or yen. By default, naive.

• exclude_edge (bool, optional) – Flag indicating whether the direct edge from the source to the target should be excluded from the result (if exists).

Returns:

paths – List containing top n best paths according to the distance score

Return type:

list

n_shortest_tripaths(source, intermediary, target, n, distance=None, strategy='naive', exclude_edge=False, overlap=True)

Compute n shortest tri-paths from the source to the target.

Tripaths cosist of two path sets, from the source (A) to the intermediary (B) and from the intermediary to the target (C). These sets can be overlapping or not. If the sets are non-overlapping, all the nodes encountered on the paths from A to B are excluded from the search of paths from B to C.

Parameters:

• source (str) – Source node ID

• intermediary (str) – Intermediate node ID

• target (str) – Target node ID

• n (int) – Number of best paths to search for

• distance (str, optional) – The name of the attribute to use as the edge distance

• exclude_edge (bool, optional) – Flag indicating whether the direct edge from the source to the target should be excluded from the result (if exists).

• overlap (bool, optional.) – Flag indicating whether the two paths are allowed to intersect (to pass through the same nodes). By default True.

Returns:

• a_b_paths (list) – List containing the shortest paths from A to B

• b_c_paths (list) – List containing the shortest paths from B to C

nested_shortest_path(source, target, depth=1, distance=None, exclude_edge=True)

Find the shortest nested path.

shortest_path(source, target, distance=None, exclude_edge=False)

Compute the single shortest path from the source to the target.

Parameters:

• source (str) – Source node ID

• target (str) – Target node ID

• exclude_edge (bool, optional) – Flag indicating whether the direct edge from the source to the target should be excluded from the result (if exists).

shortest_tripath(source, intermediary, target, distance=None, exclude_edge=False, overlap=True)

Compute the shortest tri-path from the source to the target.

The shortest tripath is given by two paths: the shortest path from the source to the intermediary and from the intermediary to the target. These sets can be overlapping or not. If the sets are non-overlapping, all the nodes encountered on the paths from A to B are excluded from the search of paths from B to C.

Parameters:

• source (str) – Source node ID

• intermediary (str) – Intermediate node ID

• target (str) – Target node ID

• distance (str, optional) – The name of the attribute to use as the edge distance

• exclude_edge (bool, optional) – Flag indicating whether the direct edge from the source to the target should be excluded from the result (if exists).

• overlap (bool, optional.) – Flag indicating whether the two paths are allowed to intersect (to pass through the same nodes). By default True.

Returns:

• a_b_path (tuple) – The shortest path from A to B

• b_c_path (tuple) – The shortest path from B to C

top_neighbors(node, n, weight, smallest=False)

Get top n neighbours of the specified node by weight.

bluegraph.core.analyse.paths.graph_elements_from_paths(paths)

Create a graph from a set of paths.

Resulting graph contains nodes and edges from the input set of paths. If the source graph is provided, the attributes of the selected nodes and edges are copied from the source graph.

bluegraph.core.analyse.paths.pretty_print_paths(paths, as_repr=False)

Pretty print a set of same source/target paths.

Community Detection

class bluegraph.core.analyse.communities.CommunityDetector

Abstract class for a community detector.

This class provides a simple interface for detecting communities of densely connected nodes and evaluating community partitions.

Currently supported community detection strategies (methods not currently implemented by specific backends return PartitionError):

• Louvain algorithm (strategy=”louvain”)

• Girvan–Newman algorithm (strategy=”girvan-newman”)

• Statistical inference (strategy=”sbm”)

• Label propagation (strategy=”lpa”)

• Hierarchical clustering (strategy=”hierarchical”)

Metrics for evaluation of partitions:

• Modularity

• Performance

• Coverage

References

• Fortunato, Santo. “Community detection in graphs.” Physics reports 486.3-5 (2010): 75-174.

• https://graph-tool.skewed.de/static/doc/demos/inference/inference.html

exception EvaluationError

exception EvaluationWarning

exception PartitionError

detect_communities(strategy='louvain', weight=None, n_communities=2, intermediate=False, write=False, write_property=None, **kwargs)

Detect community partition using the input strategy.