From da2ea7ec08c90148b962ae62fb2740716259d3f0 Mon Sep 17 00:00:00 2001 From: Douglas Fenstermacher Date: Mon, 17 May 2021 20:32:53 -0400 Subject: adds implementation of SNAP summarization algorithm (#4463) * adds implementation of SNAP summarization algorithm Thanks to dschult and rossbar for many much-needed recommendations for refining and optimizing the implementation * Seed layouts for snap gallery examples. Make sure the layouts are reproducible. Co-authored-by: Ross Barnowski --- doc/reference/algorithms/summarization.rst | 1 + examples/algorithms/plot_snap.py | 108 ++++++ networkx/algorithms/summarization.py | 355 ++++++++++++++++++- networkx/algorithms/tests/test_summarization.py | 441 +++++++++++++++++++++++- 4 files changed, 893 insertions(+), 12 deletions(-) create mode 100644 examples/algorithms/plot_snap.py diff --git a/doc/reference/algorithms/summarization.rst b/doc/reference/algorithms/summarization.rst index 3efd6237..8b8ebcb0 100644 --- a/doc/reference/algorithms/summarization.rst +++ b/doc/reference/algorithms/summarization.rst @@ -7,3 +7,4 @@ Summarization :toctree: generated/ dedensify + snap_aggregation diff --git a/examples/algorithms/plot_snap.py b/examples/algorithms/plot_snap.py new file mode 100644 index 00000000..85ea71de --- /dev/null +++ b/examples/algorithms/plot_snap.py @@ -0,0 +1,108 @@ +""" +================== +SNAP Graph Summary +================== +An example of summarizing a graph based on node attributes and edge attributes +using the Summarization by Grouping Nodes on Attributes and Pairwise +edges (SNAP) algorithm (not to be confused with the Stanford Network +Analysis Project). The algorithm groups nodes by their unique +combinations of node attribute values and edge types with other groups +of nodes to produce a summary graph. The summary graph can then be used to +infer how nodes with different attributes values relate to other nodes in the +graph. +""" +import networkx as nx +import matplotlib.pyplot as plt + + +nodes = { + "A": dict(color="Red"), + "B": dict(color="Red"), + "C": dict(color="Red"), + "D": dict(color="Red"), + "E": dict(color="Blue"), + "F": dict(color="Blue"), + "G": dict(color="Blue"), + "H": dict(color="Blue"), + "I": dict(color="Yellow"), + "J": dict(color="Yellow"), + "K": dict(color="Yellow"), + "L": dict(color="Yellow"), +} +edges = [ + ("A", "B", "Strong"), + ("A", "C", "Weak"), + ("A", "E", "Strong"), + ("A", "I", "Weak"), + ("B", "D", "Weak"), + ("B", "J", "Weak"), + ("B", "F", "Strong"), + ("C", "G", "Weak"), + ("D", "H", "Weak"), + ("I", "J", "Strong"), + ("J", "K", "Strong"), + ("I", "L", "Strong"), +] +original_graph = nx.Graph() +original_graph.add_nodes_from(n for n in nodes.items()) +original_graph.add_edges_from((u, v, {"type": label}) for u, v, label in edges) + + +plt.suptitle("SNAP Summarization") + +base_options = dict(with_labels=True, edgecolors="black", node_size=500) + +ax1 = plt.subplot(1, 2, 1) +plt.title( + "Original (%s nodes, %s edges)" + % (original_graph.number_of_nodes(), original_graph.number_of_edges()) +) +pos = nx.spring_layout(original_graph, seed=7482934) +node_colors = [d["color"] for _, d in original_graph.nodes(data=True)] + +edge_type_visual_weight_lookup = {"Weak": 1.0, "Strong": 3.0} +edge_weights = [ + edge_type_visual_weight_lookup[d["type"]] + for _, _, d in original_graph.edges(data=True) +] + +nx.draw_networkx( + original_graph, pos=pos, node_color=node_colors, width=edge_weights, **base_options +) + +node_attributes = ("color",) +edge_attributes = ("type",) +summary_graph = nx.snap_aggregation( + original_graph, node_attributes, edge_attributes, prefix="S-" +) + +plt.subplot(1, 2, 2) + +plt.title( + "SNAP Aggregation (%s nodes, %s edges)" + % (summary_graph.number_of_nodes(), summary_graph.number_of_edges()) +) +summary_pos = nx.spring_layout(summary_graph, seed=8375428) +node_colors = [] +for node in summary_graph: + color = summary_graph.nodes[node]["color"] + node_colors.append(color) + +edge_weights = [] +for edge in summary_graph.edges(): + edge_types = summary_graph.get_edge_data(*edge)["types"] + edge_weight = 0.0 + for edge_type in edge_types: + edge_weight += edge_type_visual_weight_lookup[edge_type["type"]] + edge_weights.append(edge_weight) + +nx.draw_networkx( + summary_graph, + pos=summary_pos, + node_color=node_colors, + width=edge_weights, + **base_options +) + +plt.tight_layout() +plt.show() diff --git a/networkx/algorithms/summarization.py b/networkx/algorithms/summarization.py index f909ee3e..13d7508a 100644 --- a/networkx/algorithms/summarization.py +++ b/networkx/algorithms/summarization.py @@ -59,10 +59,10 @@ For more information on graph summarization, see `Graph Summarization Methods and Applications: A Survey `_ """ import networkx as nx +from collections import Counter, defaultdict -__all__ = [ - "dedensify", -] + +__all__ = ["dedensify", "snap_aggregation"] def dedensify(G, threshold, prefix=None, copy=True): @@ -210,3 +210,352 @@ def dedensify(G, threshold, prefix=None, copy=True): G.add_edge(compression_node, node) compressor_nodes.add(compression_node) return G, compressor_nodes + + +def _snap_build_graph( + G, + groups, + node_attributes, + edge_attributes, + neighbor_info, + edge_types, + prefix, + supernode_attribute, + superedge_attribute, +): + """ + Build the summary graph from the data structures produced in the SNAP aggregation algorithm + + Used in the SNAP aggregation algorithm to build the output summary graph and supernode + lookup dictionary. This process uses the original graph and the data structures to + create the supernodes with the correct node attributes, and the superedges with the correct + edge attributes + + Parameters + ---------- + G: networkx.Graph + the original graph to be summarized + groups: dict + A dictionary of unique group IDs and their corresponding node groups + node_attributes: iterable + An iterable of the node attributes considered in the summarization process + edge_attributes: iterable + An iterable of the edge attributes considered in the summarization process + neighbor_info: dict + A data structure indicating the number of edges a node has with the + groups in the current summarization of each edge type + edge_types: dict + dictionary of edges in the graph and their corresponding attributes recognized + in the summarization + prefix: string + The prefix to be added to all supernodes + supernode_attribute: str + The node attribute for recording the supernode groupings of nodes + superedge_attribute: str + The edge attribute for recording the edge types represented by superedges + + Returns + ------- + summary graph: Networkx graph + """ + output = G.__class__() + node_label_lookup = dict() + for index, group_id in enumerate(groups): + group_set = groups[group_id] + supernode = "%s%s" % (prefix, index) + node_label_lookup[group_id] = supernode + supernode_attributes = { + attr: G.nodes[next(iter(group_set))][attr] for attr in node_attributes + } + supernode_attributes[supernode_attribute] = group_set + output.add_node(supernode, **supernode_attributes) + + for group_id in groups: + group_set = groups[group_id] + source_supernode = node_label_lookup[group_id] + for other_group, group_edge_types in neighbor_info[ + next(iter(group_set)) + ].items(): + if group_edge_types: + target_supernode = node_label_lookup[other_group] + summary_graph_edge = (source_supernode, target_supernode) + + edge_types = [ + dict(zip(edge_attributes, edge_type)) + for edge_type in group_edge_types + ] + + has_edge = output.has_edge(*summary_graph_edge) + if output.is_multigraph(): + if not has_edge: + for edge_type in edge_types: + output.add_edge(*summary_graph_edge, **edge_type) + elif not output.is_directed(): + existing_edge_data = output.get_edge_data(*summary_graph_edge) + for edge_type in edge_types: + if edge_type not in existing_edge_data.values(): + output.add_edge(*summary_graph_edge, **edge_type) + else: + superedge_attributes = {superedge_attribute: edge_types} + output.add_edge(*summary_graph_edge, **superedge_attributes) + + return output + + +def _snap_eligible_group(G, groups, group_lookup, edge_types): + """ + Determines if a group is eligible to be split. + + A group is eligible to be split if all nodes in the group have edges of the same type(s) + with the same other groups. + + Parameters + ---------- + G: graph + graph to be summarized + groups: dict + A dictionary of unique group IDs and their corresponding node groups + group_lookup: dict + dictionary of nodes and their current corresponding group ID + edge_types: dict + dictionary of edges in the graph and their corresponding attributes recognized + in the summarization + + Returns + ------- + tuple: group ID to split, and neighbor-groups participation_counts data structure + """ + neighbor_info = {node: {gid: Counter() for gid in groups} for node in group_lookup} + for group_id in groups: + current_group = groups[group_id] + + # build neighbor_info for nodes in group + for node in current_group: + neighbor_info[node] = {group_id: Counter() for group_id in groups} + edges = G.edges(node, keys=True) if G.is_multigraph() else G.edges(node) + for edge in edges: + neighbor = edge[1] + edge_type = edge_types[edge] + neighbor_group_id = group_lookup[neighbor] + neighbor_info[node][neighbor_group_id][edge_type] += 1 + + # check if group_id is eligible to be split + group_size = len(current_group) + for other_group_id in groups: + edge_counts = Counter() + for node in current_group: + edge_counts.update(neighbor_info[node][other_group_id].keys()) + + if not all(count == group_size for count in edge_counts.values()): + # only the neighbor_info of the returned group_id is required for handling group splits + return group_id, neighbor_info + + # if no eligible groups, complete neighbor_info is calculated + return None, neighbor_info + + +def _snap_split( + groups, + neighbor_info, + group_lookup, + group_id, +): + """ + Splits a group based on edge types and updates the groups accordingly + + Splits the group with the given group_id based on the edge types + of the nodes so that each new grouping will all have the same + edges with other nodes. + + Parameters + ---------- + groups: dict + A dictionary of unique group IDs and their corresponding node groups + neighbor_info: dict + A data structure indicating the number of edges a node has with the + groups in the current summarization of each edge type + edge_types: dict + dictionary of edges in the graph and their corresponding attributes recognized + in the summarization + group_lookup: dict + dictionary of nodes and their current corresponding group ID + group_id: object + ID of group to be split + + Returns + ------- + dict + The updated groups based on the split + """ + new_group_mappings = defaultdict(set) + for node in groups[group_id]: + signature = tuple( + frozenset(edge_types) for edge_types in neighbor_info[node].values() + ) + new_group_mappings[signature].add(node) + + # leave the biggest new_group as the original group + new_groups = sorted(new_group_mappings.values(), key=len) + for new_group in new_groups[:-1]: + # Assign unused integer as the new_group_id + # ids are tuples, so will not interact with the original group_ids + new_group_id = len(groups) + groups[new_group_id] = new_group + groups[group_id] -= new_group + for node in new_group: + group_lookup[node] = new_group_id + + return groups + + +def snap_aggregation( + G, + node_attributes, + edge_attributes=(), + prefix="Supernode-", + supernode_attribute="group", + superedge_attribute="types", +): + """Creates a summary graph based on attributes and connectivity. + + This function uses the Summarization by Grouping Nodes on Attributes + and Pairwise edges (SNAP) algorithm for summarizing a given + graph by grouping nodes by node attributes and their edge attributes + into supernodes in a summary graph. This name SNAP should not be + confused with the Stanford Network Analysis Project (SNAP). + + Here is a high-level view of how this algorithm works: + + 1) Group nodes by node attribute values. + + 2) Iteratively split groups until all nodes in each group have edges + to nodes in the same groups. That is, until all the groups are homogeneous + in their member nodes' edges to other groups. For example, + if all the nodes in group A only have edge to nodes in group B, then the + group is homogeneous and does not need to be split. If all nodes in group B + have edges with nodes in groups {A, C}, but some also have edges with other + nodes in B, then group B is not homogeneous and needs to be split into + groups have edges with {A, C} and a group of nodes having + edges with {A, B, C}. This way, viewers of the summary graph can + assume that all nodes in the group have the exact same node attributes and + the exact same edges. + + 3) Build the output summary graph, where the groups are represented by + super-nodes. Edges represent the edges shared between all the nodes in each + respective groups. + + A SNAP summary graph can be used to visualize graphs that are too large to display + or visually analyze, or to efficiently identify sets of similar nodes with similar connectivity + patterns to other sets of similar nodes based on specified node and/or edge attributes in a graph. + + Parameters + ---------- + G: graph + Networkx Graph to be summarized + edge_attributes: iterable, optional + An iterable of the edge attributes considered in the summarization process. If provided, unique + combinations of the attribute values found in the graph are used to + determine the edge types in the graph. If not provided, all edges + are considered to be of the same type. + prefix: str + The prefix used to denote supernodes in the summary graph. Defaults to 'Supernode-'. + supernode_attribute: str + The node attribute for recording the supernode groupings of nodes. Defaults to 'group'. + superedge_attribute: str + The edge attribute for recording the edge types of multiple edges. Defaults to 'types'. + + Returns + ------- + networkx.Graph: summary graph + + Examples + -------- + SNAP aggregation takes a graph and summarizes it in the context of user-provided + node and edge attributes such that a viewer can more easily extract and + analyze the information represented by the graph:: + + >>> nodes = { + ... "A": dict(color="Red"), + ... "B": dict(color="Red"), + ... "C": dict(color="Red"), + ... "D": dict(color="Red"), + ... "E": dict(color="Blue"), + ... "F": dict(color="Blue"), + ... } + >>> edges = [ + ... ("A", "E", "Strong"), + ... ("B", "F", "Strong"), + ... ("C", "E", "Weak"), + ... ("D", "F", "Weak"), + ... ] + >>> G = nx.Graph() + >>> for node in nodes: + ... attributes = nodes[node] + ... G.add_node(node, **attributes) + ... + >>> for source, target, type in edges: + ... G.add_edge(source, target, type=type) + ... + >>> node_attributes = ('color', ) + >>> edge_attributes = ('type', ) + >>> summary_graph = nx.snap_aggregation(G, node_attributes=node_attributes, edge_attributes=edge_attributes) + + Notes + ----- + The summary graph produced is called a maximum Attribute-edge + compatible (AR-compatible) grouping. According to [1]_, an + AR-compatible grouping means that all nodes in each group have the same + exact node attribute values and the same exact edges and + edge types to one or more nodes in the same groups. The maximal + AR-compatible grouping is the grouping with the minimal cardinality. + + The AR-compatible grouping is the most detailed grouping provided by + any of the SNAP algorithms. + + References + ---------- + .. [1] Y. Tian, R. A. Hankins, and J. M. Patel. Efficient aggregation + for graph summarization. In Proc. 2008 ACM-SIGMOD Int. Conf. + Management of Data (SIGMOD’08), pages 567–580, Vancouver, Canada, + June 2008. + """ + edge_types = { + edge: tuple(attrs.get(attr) for attr in edge_attributes) + for edge, attrs in G.edges.items() + } + if not G.is_directed(): + if G.is_multigraph(): + # list is needed to avoid mutating while iterating + edges = [((v, u, k), etype) for (u, v, k), etype in edge_types.items()] + else: + # list is needed to avoid mutating while iterating + edges = [((v, u), etype) for (u, v), etype in edge_types.items()] + edge_types.update(edges) + + group_lookup = { + node: tuple(attrs[attr] for attr in node_attributes) + for node, attrs in G.nodes.items() + } + groups = defaultdict(set) + for node, node_type in group_lookup.items(): + groups[node_type].add(node) + + eligible_group_id, neighbor_info = _snap_eligible_group( + G, groups, group_lookup, edge_types + ) + while eligible_group_id: + groups = _snap_split(groups, neighbor_info, group_lookup, eligible_group_id) + eligible_group_id, neighbor_info = _snap_eligible_group( + G, groups, group_lookup, edge_types + ) + return _snap_build_graph( + G, + groups, + node_attributes, + edge_attributes, + neighbor_info, + edge_types, + prefix, + supernode_attribute, + superedge_attribute, + ) diff --git a/networkx/algorithms/tests/test_summarization.py b/networkx/algorithms/tests/test_summarization.py index 4140a504..dd90d0b9 100644 --- a/networkx/algorithms/tests/test_summarization.py +++ b/networkx/algorithms/tests/test_summarization.py @@ -1,9 +1,8 @@ """ -Unit tests for dedensification/densification +Unit tests for dedensification and graph summarization """ - +import pytest import networkx as nx -from networkx.algorithms.summarization import dedensify class TestDirectedDedensification: @@ -45,7 +44,7 @@ class TestDirectedDedensification: Verify that an empty directed graph results in no compressor nodes """ G = nx.DiGraph() - compressed_graph, c_nodes = dedensify(G, threshold=2) + compressed_graph, c_nodes = nx.dedensify(G, threshold=2) assert c_nodes == set() @staticmethod @@ -92,7 +91,7 @@ class TestDirectedDedensification: """ G = self.build_original_graph() compressed_G = self.build_compressed_graph() - compressed_graph, c_nodes = dedensify(G, threshold=2) + compressed_graph, c_nodes = nx.dedensify(G, threshold=2) for s, t in compressed_graph.edges(): o_s = "".join(sorted(s)) o_t = "".join(sorted(t)) @@ -108,7 +107,7 @@ class TestDirectedDedensification: """ G = self.build_original_graph() original_edge_count = len(G.edges()) - c_G, c_nodes = dedensify(G, threshold=2) + c_G, c_nodes = nx.dedensify(G, threshold=2) compressed_edge_count = len(c_G.edges()) assert compressed_edge_count <= original_edge_count compressed_G = self.build_compressed_graph() @@ -164,7 +163,7 @@ class TestUnDirectedDedensification: Verify that an empty undirected graph results in no compressor nodes """ G = nx.Graph() - compressed_G, c_nodes = dedensify(G, threshold=2) + compressed_G, c_nodes = nx.dedensify(G, threshold=2) assert c_nodes == set() def setup_method(self): @@ -197,7 +196,7 @@ class TestUnDirectedDedensification: correct edges to/from the compressor nodes in an undirected graph """ G = self.build_original_graph() - c_G, c_nodes = dedensify(G, threshold=2) + c_G, c_nodes = nx.dedensify(G, threshold=2) v_compressed_G = self.build_compressed_graph() for s, t in c_G.edges(): o_s = "".join(sorted(s)) @@ -213,10 +212,434 @@ class TestUnDirectedDedensification: undirected graph """ G = self.build_original_graph() - c_G, c_nodes = dedensify(G, threshold=2, copy=True) + c_G, c_nodes = nx.dedensify(G, threshold=2, copy=True) compressed_edge_count = len(c_G.edges()) verified_original_edge_count = len(G.edges()) assert compressed_edge_count <= verified_original_edge_count verified_compressed_G = self.build_compressed_graph() verified_compressed_edge_count = len(verified_compressed_G.edges()) assert compressed_edge_count == verified_compressed_edge_count + + +@pytest.mark.parametrize( + "graph_type", [nx.Graph, nx.DiGraph, nx.MultiGraph, nx.MultiDiGraph] +) +def test_summarization_empty(graph_type): + G = graph_type() + summary_graph = nx.snap_aggregation(G, node_attributes=("color",)) + assert nx.is_isomorphic(summary_graph, G) + + +class AbstractSNAP: + node_attributes = ("color",) + + def build_original_graph(self): + pass + + def build_summary_graph(self): + pass + + def test_summary_graph(self): + original_graph = self.build_original_graph() + summary_graph = self.build_summary_graph() + + relationship_attributes = ("type",) + generated_summary_graph = nx.snap_aggregation( + original_graph, + self.node_attributes, + relationship_attributes, + ) + relabeled_summary_graph = self.deterministic_labels(generated_summary_graph) + assert nx.is_isomorphic(summary_graph, relabeled_summary_graph) + + def deterministic_labels(self, G): + node_labels = list(G.nodes) + node_labels = sorted(node_labels, key=lambda n: sorted(G.nodes[n]["group"])[0]) + node_labels.sort() + + label_mapping = dict() + for index, node in enumerate(node_labels): + label = "Supernode-%s" % index + label_mapping[node] = label + + return nx.relabel_nodes(G, label_mapping) + + +class TestSNAPNoEdgeTypes(AbstractSNAP): + relationship_attributes = () + + def test_summary_graph(self): + original_graph = self.build_original_graph() + summary_graph = self.build_summary_graph() + + relationship_attributes = ("type",) + generated_summary_graph = nx.snap_aggregation( + original_graph, self.node_attributes + ) + relabeled_summary_graph = self.deterministic_labels(generated_summary_graph) + assert nx.is_isomorphic(summary_graph, relabeled_summary_graph) + + def build_original_graph(self): + nodes = { + "A": dict(color="Red"), + "B": dict(color="Red"), + "C": dict(color="Red"), + "D": dict(color="Red"), + "E": dict(color="Blue"), + "F": dict(color="Blue"), + "G": dict(color="Blue"), + "H": dict(color="Blue"), + "I": dict(color="Yellow"), + "J": dict(color="Yellow"), + "K": dict(color="Yellow"), + "L": dict(color="Yellow"), + } + edges = [ + ("A", "B"), + ("A", "C"), + ("A", "E"), + ("A", "I"), + ("B", "D"), + ("B", "J"), + ("B", "F"), + ("C", "G"), + ("D", "H"), + ("I", "J"), + ("J", "K"), + ("I", "L"), + ] + G = nx.Graph() + for node in nodes: + attributes = nodes[node] + G.add_node(node, **attributes) + + for source, target in edges: + G.add_edge(source, target) + + return G + + def build_summary_graph(self): + nodes = { + "Supernode-0": dict(color="Red"), + "Supernode-1": dict(color="Red"), + "Supernode-2": dict(color="Blue"), + "Supernode-3": dict(color="Blue"), + "Supernode-4": dict(color="Yellow"), + "Supernode-5": dict(color="Yellow"), + } + edges = [ + ("Supernode-0", "Supernode-0"), + ("Supernode-0", "Supernode-1"), + ("Supernode-0", "Supernode-2"), + ("Supernode-0", "Supernode-4"), + ("Supernode-1", "Supernode-3"), + ("Supernode-4", "Supernode-4"), + ("Supernode-4", "Supernode-5"), + ] + G = nx.Graph() + for node in nodes: + attributes = nodes[node] + G.add_node(node, **attributes) + + for source, target in edges: + G.add_edge(source, target) + + supernodes = { + "Supernode-0": set(["A", "B"]), + "Supernode-1": set(["C", "D"]), + "Supernode-2": set(["E", "F"]), + "Supernode-3": set(["G", "H"]), + "Supernode-4": set(["I", "J"]), + "Supernode-5": set(["K", "L"]), + } + nx.set_node_attributes(G, supernodes, "group") + return G + + +class TestSNAPUndirected(AbstractSNAP): + def build_original_graph(self): + nodes = { + "A": dict(color="Red"), + "B": dict(color="Red"), + "C": dict(color="Red"), + "D": dict(color="Red"), + "E": dict(color="Blue"), + "F": dict(color="Blue"), + "G": dict(color="Blue"), + "H": dict(color="Blue"), + "I": dict(color="Yellow"), + "J": dict(color="Yellow"), + "K": dict(color="Yellow"), + "L": dict(color="Yellow"), + } + edges = [ + ("A", "B", "Strong"), + ("A", "C", "Weak"), + ("A", "E", "Strong"), + ("A", "I", "Weak"), + ("B", "D", "Weak"), + ("B", "J", "Weak"), + ("B", "F", "Strong"), + ("C", "G", "Weak"), + ("D", "H", "Weak"), + ("I", "J", "Strong"), + ("J", "K", "Strong"), + ("I", "L", "Strong"), + ] + G = nx.Graph() + for node in nodes: + attributes = nodes[node] + G.add_node(node, **attributes) + + for source, target, type in edges: + G.add_edge(source, target, type=type) + + return G + + def build_summary_graph(self): + nodes = { + "Supernode-0": dict(color="Red"), + "Supernode-1": dict(color="Red"), + "Supernode-2": dict(color="Blue"), + "Supernode-3": dict(color="Blue"), + "Supernode-4": dict(color="Yellow"), + "Supernode-5": dict(color="Yellow"), + } + edges = [ + ("Supernode-0", "Supernode-0", "Strong"), + ("Supernode-0", "Supernode-1", "Weak"), + ("Supernode-0", "Supernode-2", "Strong"), + ("Supernode-0", "Supernode-4", "Weak"), + ("Supernode-1", "Supernode-3", "Weak"), + ("Supernode-4", "Supernode-4", "Strong"), + ("Supernode-4", "Supernode-5", "Strong"), + ] + G = nx.Graph() + for node in nodes: + attributes = nodes[node] + G.add_node(node, **attributes) + + for source, target, type in edges: + G.add_edge(source, target, types=[dict(type=type)]) + + supernodes = { + "Supernode-0": set(["A", "B"]), + "Supernode-1": set(["C", "D"]), + "Supernode-2": set(["E", "F"]), + "Supernode-3": set(["G", "H"]), + "Supernode-4": set(["I", "J"]), + "Supernode-5": set(["K", "L"]), + } + nx.set_node_attributes(G, supernodes, "group") + return G + + +class TestSNAPDirected(AbstractSNAP): + def build_original_graph(self): + nodes = { + "A": dict(color="Red"), + "B": dict(color="Red"), + "C": dict(color="Green"), + "D": dict(color="Green"), + "E": dict(color="Blue"), + "F": dict(color="Blue"), + "G": dict(color="Yellow"), + "H": dict(color="Yellow"), + } + edges = [ + ("A", "C", "Strong"), + ("A", "E", "Strong"), + ("A", "F", "Weak"), + ("B", "D", "Strong"), + ("B", "E", "Weak"), + ("B", "F", "Strong"), + ("C", "G", "Strong"), + ("C", "F", "Strong"), + ("D", "E", "Strong"), + ("D", "H", "Strong"), + ("G", "E", "Strong"), + ("H", "F", "Strong"), + ] + G = nx.DiGraph() + for node in nodes: + attributes = nodes[node] + G.add_node(node, **attributes) + + for source, target, type in edges: + G.add_edge(source, target, type=type) + + return G + + def build_summary_graph(self): + nodes = { + "Supernode-0": dict(color="Red"), + "Supernode-1": dict(color="Green"), + "Supernode-2": dict(color="Blue"), + "Supernode-3": dict(color="Yellow"), + } + edges = [ + ("Supernode-0", "Supernode-1", [{"type": "Strong"}]), + ("Supernode-0", "Supernode-2", [{"type": "Weak"}, {"type": "Strong"}]), + ("Supernode-1", "Supernode-2", [{"type": "Strong"}]), + ("Supernode-1", "Supernode-3", [{"type": "Strong"}]), + ("Supernode-3", "Supernode-2", [{"type": "Strong"}]), + ] + G = nx.DiGraph() + for node in nodes: + attributes = nodes[node] + G.add_node(node, **attributes) + + for source, target, types in edges: + G.add_edge(source, target, types=types) + + supernodes = { + "Supernode-0": set(["A", "B"]), + "Supernode-1": set(["C", "D"]), + "Supernode-2": set(["E", "F"]), + "Supernode-3": set(["G", "H"]), + "Supernode-4": set(["I", "J"]), + "Supernode-5": set(["K", "L"]), + } + nx.set_node_attributes(G, supernodes, "group") + return G + + +class TestSNAPUndirectedMulti(AbstractSNAP): + def build_original_graph(self): + nodes = { + "A": dict(color="Red"), + "B": dict(color="Red"), + "C": dict(color="Red"), + "D": dict(color="Blue"), + "E": dict(color="Blue"), + "F": dict(color="Blue"), + "G": dict(color="Yellow"), + "H": dict(color="Yellow"), + "I": dict(color="Yellow"), + } + edges = [ + ("A", "D", ["Weak", "Strong"]), + ("B", "E", ["Weak", "Strong"]), + ("D", "I", ["Strong"]), + ("E", "H", ["Strong"]), + ("F", "G", ["Weak"]), + ("I", "G", ["Weak", "Strong"]), + ("I", "H", ["Weak", "Strong"]), + ("G", "H", ["Weak", "Strong"]), + ] + G = nx.MultiGraph() + for node in nodes: + attributes = nodes[node] + G.add_node(node, **attributes) + + for source, target, types in edges: + for type in types: + G.add_edge(source, target, type=type) + + return G + + def build_summary_graph(self): + nodes = { + "Supernode-0": dict(color="Red"), + "Supernode-1": dict(color="Blue"), + "Supernode-2": dict(color="Yellow"), + "Supernode-3": dict(color="Blue"), + "Supernode-4": dict(color="Yellow"), + "Supernode-5": dict(color="Red"), + } + edges = [ + ("Supernode-1", "Supernode-2", [{"type": "Weak"}]), + ("Supernode-2", "Supernode-4", [{"type": "Weak"}, {"type": "Strong"}]), + ("Supernode-3", "Supernode-4", [{"type": "Strong"}]), + ("Supernode-3", "Supernode-5", [{"type": "Weak"}, {"type": "Strong"}]), + ("Supernode-4", "Supernode-4", [{"type": "Weak"}, {"type": "Strong"}]), + ] + G = nx.MultiGraph() + for node in nodes: + attributes = nodes[node] + G.add_node(node, **attributes) + + for source, target, types in edges: + for type in types: + G.add_edge(source, target, type=type) + + supernodes = { + "Supernode-0": set(["A", "B"]), + "Supernode-1": set(["C", "D"]), + "Supernode-2": set(["E", "F"]), + "Supernode-3": set(["G", "H"]), + "Supernode-4": set(["I", "J"]), + "Supernode-5": set(["K", "L"]), + } + nx.set_node_attributes(G, supernodes, "group") + return G + + +class TestSNAPDirectedMulti(AbstractSNAP): + def build_original_graph(self): + nodes = { + "A": dict(color="Red"), + "B": dict(color="Red"), + "C": dict(color="Green"), + "D": dict(color="Green"), + "E": dict(color="Blue"), + "F": dict(color="Blue"), + "G": dict(color="Yellow"), + "H": dict(color="Yellow"), + } + edges = [ + ("A", "C", ["Weak", "Strong"]), + ("A", "E", ["Strong"]), + ("A", "F", ["Weak"]), + ("B", "D", ["Weak", "Strong"]), + ("B", "E", ["Weak"]), + ("B", "F", ["Strong"]), + ("C", "G", ["Weak", "Strong"]), + ("C", "F", ["Strong"]), + ("D", "E", ["Strong"]), + ("D", "H", ["Weak", "Strong"]), + ("G", "E", ["Strong"]), + ("H", "F", ["Strong"]), + ] + G = nx.MultiDiGraph() + for node in nodes: + attributes = nodes[node] + G.add_node(node, **attributes) + + for source, target, types in edges: + for type in types: + G.add_edge(source, target, type=type) + + return G + + def build_summary_graph(self): + nodes = { + "Supernode-0": dict(color="Red"), + "Supernode-1": dict(color="Blue"), + "Supernode-2": dict(color="Yellow"), + "Supernode-3": dict(color="Blue"), + } + edges = [ + ("Supernode-0", "Supernode-1", ["Weak", "Strong"]), + ("Supernode-0", "Supernode-2", ["Weak", "Strong"]), + ("Supernode-1", "Supernode-2", ["Strong"]), + ("Supernode-1", "Supernode-3", ["Weak", "Strong"]), + ("Supernode-3", "Supernode-2", ["Strong"]), + ] + G = nx.MultiDiGraph() + for node in nodes: + attributes = nodes[node] + G.add_node(node, **attributes) + + for source, target, types in edges: + for type in types: + G.add_edge(source, target, type=type) + + supernodes = { + "Supernode-0": set(["A", "B"]), + "Supernode-1": set(["C", "D"]), + "Supernode-2": set(["E", "F"]), + "Supernode-3": set(["G", "H"]), + } + nx.set_node_attributes(G, supernodes, "group") + return G -- cgit v1.2.1