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.