straph.components package

Submodules

straph.components.UnionFindSCC module

straph.components.UnionFindSCC.dynamic_connectivity(E, SCC, times)[source]
straph.components.UnionFindSCC.get_pred_and_suc(value, times)[source]

Return the predecessor and the successor of the value as well as the predecessor of the predecessor of the value in the array times.

Parameters

  • value – float

  • times – SortedSet

Returns

straph.components.UnionFindSCC.postprocess_SCC(SCC)[source]

Postprocess SCC into clusters.

Parameters

SCC – List of SCC returned by SCC-UF Algorithm

Returns

A list of clusters

straph.components.UnionFindSCC.strongly_connected_components_UF(S, format='cluster')[source]

Compute the Strongly Connected Components of a StreamGraph with SCC-UF Algorithm.

Parameters

  • S – A StreamGraph object

  • format – The format of the output, only ‘cluster’ is currently available.

Returns

A list of clusters.

straph.components.component module

class straph.components.component.ConnectedComponent(id=None, times=None, nodes=None, active_links=None, links=None)[source]

Bases: object

add_node(n)[source]
adjacency_list_at_t(t)[source]

Return the adjacency list of the induced instant graph at time t of the component.

Parameters

t – A time instantin the component’s time window

Returns

A dictionary

clear()[source]

Clear the component

Returns

degrees()[source]

Return the nodes degree in the aggregated graph induced by the component.

Returns

A dictionary associating each node to its degree

get_interactions_times()[source]

Return the set of interactions times in the component.

Returns

A set.

get_nodes()[source]

Retrieve the nodes in the component based on its set of present links (active_links)

Returns

A set of nodes

is_connected()[source]

Return True if the component is connected, False otherwise.

Returns

A boolean

merge(comp)[source]

Merge the component comp into the current one.

Parameters

comp – Another ConnectedComponent object

Returns

Nothing, it modify inplace the current component.

plot(plot_links=True, title=None)[source]

Display the ConnectedComponent using matplotlib

Parameters

  • plot_links – To display links in the component

  • title – Figure title

Returns

A matplotlib figure

random_path(source, destination, rand_time=False)[source]

Return a random path between the source and the destination inside the component

Parameters

  • source – A source node

  • destination – A destination node

  • rand_time – Force the path to occur at a random instant in the component (optional).

Returns

A random path in the component

random_path_pw()[source]

Return random paths between every node (pairwise)

Returns

random_path_ss(source)[source]

Return random paths between the source and all the other nodes in the component.

Parameters

source – A souce node

Returns

remove_node(n)[source]
set_begin_time(t)[source]
set_end_time(t)[source]
set_id(id)[source]
size()[source]

Return the size of the component, its number of nodes

Returns

The component size (an integer)

split()[source]

Split the component based on its active_links. This method is only used in connected component algorithms.

Returns

A list containing the (nodes, links, set_links) of the connected components stemming from the current component.

surface()[source]

The component’s surface is defined as the sum of its links presence.

Returns

The component’s surface (a float).

to_adjacency_list(ordering=None)[source]

Return the adjacency list corresponding to the links present in the component. An assumption is made, the component must be equivalent to a static graph as we return the adjacency list of the aggregated component.

Parameters

ordering – Dictionary providing an ordering for the component’s nodes, the associated adjacency list will be directed. A directed edge between u and v will only be created if ordering[u] < ordering[v].

Returns

The component adjacency list (a dictionnary).

straph.components.stable_connected_component module

class straph.components.stable_connected_component.StableConnectedComponent(id=None, times=None, nodes=None, active_links=None, links=None, clusters=None)[source]

Bases: straph.components.component.ConnectedComponent

all_cliques()[source]
core_number()[source]
k_clique(k)[source]
k_core(k)[source]
split()[source]

Split the component based on its active_links. This method is only used in connected component algorithms.

Returns

A list containing the (nodes, links, set_links) of the connected components stemming from the current component.

straph.components.stable_connected_component.algo_kcliques_KCList(k, a_l, node_label, C=None, R=None)[source]

Compute k_cliques of a static graph from its core odering dag. .. rubric:: References

[2] Listing k-cliques in Sparse Real-World Graphs Maximilien Danisch, et al., 2018 https://dl.acm.org/citation.cfm?id=3186125

Parameters

  • k – The parameter k, number of nodes in the considered cliques

  • a_l – Adjacency list of the core ordering dag

  • node_label – label of each node

  • C – List of current cliques

  • R – List of completed cliques

Returns

The k_cliques of the graph.

straph.components.stable_connected_component.algo_kcores_batagelj(a_l, degrees, core_ordering=False)[source]

Compute k_cores of a static graph from its adjacency list and nodes degrees .. rubric:: References

[1] An O(m) Algorithm for Cores Decomposition of Networks Vladimir Batagelj and Matjaz Zaversnik, 2003. http://arxiv.org/abs/cs.DS/0310049

Parameters

  • a_l –

  • degrees –

  • core_ordering –

Returns

The core number of each node in the graph

straph.components.stable_connected_component.close_component(comp, t, final_components, cnt_scc_id, stable_dag=None, format='cluster', streaming_output=None, node_list=None)[source]

Close current component

Parameters

  • streaming_output –

  • node_list –

  • comp –

  • t –

  • final_components –

  • cnt_scc_id –

  • stable_dag –

  • format –

Returns

straph.components.stable_connected_component.compute_stable_connected_components(S, format='object_with_links', stable_dag=False, isolated_nodes=True, streaming_output=None, free_memory=False, node_list=None)[source]

Compute the Stable Connected Components (StCC) of a Stream Graph.

Parameters

  • node_list –

  • free_memory –

  • streaming_output –

  • isolated_nodes –

  • S – A StreamGraph object

  • format – Format of the output can be “cluster” or “object” or “object_with_links”

  • stable_dag – Boolean, true if we want to output the Condensation DAG, false otherwise

Returns

straph.components.stable_connected_component.create_scc(l, node_2_status, tmp_components, format='cluster')[source]

Create a Strongly Connected Component from the link l

Parameters

  • format –

  • l –

  • node_2_status –

  • tmp_components –

Returns

straph.components.stable_connected_component.get_graph_from_ordering(t0, t1, links, ordering)[source]
straph.components.stable_connected_component.merge_scc(l, node_2_status, tmp_components, final_components, stable_dag=None, cnt_scc_id=None, format='cluster', streaming_output=None, node_list=None)[source]
Parameters

  • node_list –

  • streaming_output –

  • batch –

  • node_2_status –

  • tmp_components –

  • final_components –

  • stable_dag –

  • format –

  • cnt_scc_id –

Returns

straph.components.stable_connected_component.update_scc(node_to_update, node_to_add, l, node_2_status, tmp_components, final_components, stable_dag=None, cnt_scc_id=None, format='cluster', streaming_output=None, node_list=None)[source]
Parameters

  • node_list –

  • streaming_output –

  • format –

  • final_components –

  • node_to_update –

  • node_to_add –

  • l –

  • node_2_status –

  • tmp_components –

  • stable_dag –

  • cnt_scc_id –

Returns

straph.components.strongly_connected_component module

class straph.components.strongly_connected_component.StronglyConnectedComponent(id=None, times=None, nodes=None, active_links=None, links=None)[source]

Bases: straph.components.component.ConnectedComponent

get_stable_components(format='object')[source]

Compute the stable connected components included in the current StronglyConnectedComponent

Parameters

format –

Returns

A list of StableConnectedComponents objects

split()[source]

Split the component based on its active_links. This method is only used in connected component algorithms.

Returns

A list containing the (nodes, links, set_links) of the connected components stemming from the current component.

straph.components.strongly_connected_component.close_component(comp, t, final_components, cnt_scc_id, condensation_dag=None, format='cluster', streaming_output=None)[source]

Close current component

Parameters

  • streaming_output –

  • comp –

  • t –

  • final_components –

  • cnt_scc_id –

  • condensation_dag –

  • format –

Returns

straph.components.strongly_connected_component.compute_strongly_connected_components(S, format='object_with_links', condensation_dag=False, isolated_nodes=True, streaming_output=None, free_memory=False)[source]

Compute Strongly Connected Components (SCC) of a StreamGraph.

Parameters

  • free_memory –

  • streaming_output –

  • isolated_nodes –

  • S – A Stream Graph

  • format – Format of the output can be “cluster” or “scc_object”

  • condensation_dag – Boolean, true if we want to output the Condensation DAG, false otherwise

Returns

straph.components.strongly_connected_component.create_scc(l, node_2_status, tmp_components, format='cluster')[source]

Create a Strongly Connected Component from the link l

Parameters

  • format –

  • l –

  • node_2_status –

  • tmp_components –

Returns

straph.components.strongly_connected_component.merge_scc(l, node_2_status, tmp_components, final_components, condensation_dag=None, cnt_scc_id=None, format='cluster', streaming_output=None)[source]
Parameters

  • streaming_output –

  • batch –

  • node_2_status –

  • tmp_components –

  • final_components –

  • condensation_dag –

  • format –

  • cnt_scc_id –

Returns

straph.components.strongly_connected_component.update_scc(node_to_update, node_to_add, l, node_2_status, tmp_components, final_components, condensation_dag=None, cnt_scc_id=None, format='cluster', streaming_output=None)[source]
Parameters

  • streaming_output –

  • format –

  • final_components –

  • node_to_update –

  • node_to_add –

  • l –

  • node_2_status –

  • tmp_components –

  • condensation_dag –

  • cnt_scc_id –

Returns

straph.components.weakly_connected_component module

straph.components.weakly_connected_component.compute_wcc_as_substreams(S, n_jobs=- 1)[source]

Return the weakly connected components a StreamGraph as substreams (a stream graph induced by the component/cluster)

Parameters

  • S – A StreamGraph object

  • n_jobs – Number of cores to allocate for a parallel computation.

Returns

A list of StreamGraph objects, one for each WCC.

straph.components.weakly_connected_component.compute_wcc_dfs(S, free_memory=False)[source]

Compute the Weakly Connected Components of a StreamGraph using a Depth First Search procedure.

Parameters

  • S – A StreamGraph object.

  • free_memory – Optional parameter to free some memore. WARNING: It does impact the original StreamGraph object

Returns

straph.components.weakly_connected_component.compute_wcc_streaming(S, reformat=True, free_memory=False)[source]

Compute the Weakly Connected Components of a StreamGraph in a streaming fashion with the Union-Find algorithm.

Parameters

  • S – A StreamGraph object.

  • reformat – If False, output a dictionary associating each root node to its child node (the other member of its wcc). If True, output WCC as a list of clusters.

  • free_memory – Optional parameter to free some memore. WARNING: It does impact the original StreamGraph object

Returns

Depends on the ‘reformat’ parameter. By default, a list of clusters.

straph.components.weakly_connected_component.find_node(u, dict_components)[source]

Module contents