from __future__ import print_function, division, unicode_literals, absolute_import, generators
# -*- coding: utf-8 -*-
"""
Created on Mon Apr 28 18:44:40 2014
@author: Alex
"""
from .tools import *
[docs]def node_degree_merge(g1, g2):
"""Creates merged graph following the Barabási-Albert model by adding nodes in order
of their node-degree.
Merged graph g is grown by attaching the nodes of g1 and g2 in order of their node degree
each with m edges that are preferentially attached to existing nodes with high degree.
Parameters
----------
g1 : Graph
Graph where nodes will be added
g2 : Graph
nodes which will be added to graph g
Returns
-------
g : Graph
merged Graph
"""
m = estimate_m(g1, g2, True)
return barabasi_graph(sort_nodes_by_degree(g1, g2), m)
[docs]def random_merge(g1, g2):
"""Creates merged graph following the Barabási-Albert model by adding nodes in random order.
Merged graph g is grown by attaching the nodes of g1 and g2 in random order
each with m edges that are preferentially attached to existing nodes with high degree.
Parameters
----------
g1 : Graph
Graph where nodes will be added
g2 : Graph
nodes which will be added to graph g
Returns
-------
g : Graph
merged Graph
"""
nodes = g1.nodes() + g2.nodes()
#shuffle nodes inplace
random.shuffle(nodes)
m = estimate_m(g1, g2, True)
return barabasi_graph(nodes, m)
[docs]def preserving_nodes_merge(g1, g2, add_in_order=True):
"""Creates merged graph following the Barabási-Albert model by adding nodes of g2 to graph 1.
Merged graph g is grown by attaching the nodes of g2 to the graph g1.
The estimated m of g1 will be used for the preferential attachment process.
This will result in a minimal change of g1.
Nodes of g2 are either added in order of their node degree (highest first) or in random order.
Parameters
----------
g1 : Graph
Graph will be used as basis for merged graph
g2 : Graph
Nodes of Graph 2 will be added to g1
add_in_order: boolean, optional
Should nodes be sorted befor adding them to graph g1? (default = True)
True: nodes of g2 will be added in order of their node degree
False: nodes of g2 will be added in random order
Returns
-------
g : Graph
merged Graph
"""
m = estimate_m(g1)
if add_in_order:
g = add_nodes_to_barabasi_graph(g1.copy(), sort_nodes_by_degree(g2), m)
else:
nodes_to_add = g2.nodes()
random.shuffle(nodes_to_add)
g = add_nodes_to_barabasi_graph(g1.copy(), nodes_to_add, m)
return g
[docs]def minimal_merge(g1, g2):
""" Connects both graphs with minimal amount of edges
Adds a minimal amount of edges to connect g1 and g2. Therefore choose one node per graph
by preferential attachment strategy and connect both.
Parameters
----------
g1 : Graph
Graph 1
g2 : Graph
Graph 2
Returns
-------
g : Graph
merged Graph
"""
merged_graph = nx.compose(g1, g2)
m = estimate_m(g1, g2)
n = len(merged_graph.nodes())
desired_e = ((n-m)*m) + (m*(m-1)/2)
edges_to_add = desired_e - len(merged_graph.edges())
targets_1 = get_repeated_node_list(g1)
targets_2 = get_repeated_node_list(g2)
while edges_to_add > 0:
node_1 = random.choice(targets_1)
node_2 = random.choice(targets_2)
merged_graph.add_edge(node_1, node_2)
targets_1.append(node_1)
targets_2.append(node_2)
edges_to_add -= 1
return merged_graph
if __name__ == "__main__":
G1 = barabasi_graph(["A" + str(i) for i in range(1000)], 4)
node_labels_1 = G1.nodes()
node_degrees = G1.degree().values()
G2 = barabasi_graph(["B" + str(i) for i in range(1000)], 4)
node_labels_2 = G2.nodes()
node_degrees = G2.degree().values()
print("estimated m of g1 = ", estimate_m(G1))
print("estimated m of g2 = ", estimate_m(G2))
print("estimated m of g12 = ", estimate_m(G1, G2))
print("\nRandom Merge")
randomGraph = random_merge(G1, G2)
compare_merge(randomGraph, G1, G2)
print("\nPriority Merge")
priorityGraph = node_degree_merge(G1, G2)
compare_merge(priorityGraph, G1, G2)
print("\nGraph Preserving Merge")
print("Preserve Graph 1 Merge adding nodes of graph 2 in random order")
preserveGraph1_random = preserving_nodes_merge(G1, G2, False)
compare_merge(preserveGraph1_random, G1, G2)
print("\nPreserve Graph 1 Merge adding nodes of graph 2 ordered by node degree")
preserveGraph1_ordered = preserving_nodes_merge(G1, G2, True)
compare_merge(preserveGraph1_ordered, G1, G2)
print("\nPreserve Graph 2 Merge adding nodes of graph 1 in random order")
preserveGraph2_random = preserving_nodes_merge(G2, G1, False)
compare_merge(preserveGraph2_random, G1, G2)
print("\nPreserve Graph 2 Merge adding nodes of graph 1 ordered by node degree")
preserveGraph2_ordered = preserving_nodes_merge(G2, G1, True)
compare_merge(preserveGraph1_ordered, G1, G2)
print("\nMinimal Merge")
minimalGraph = minimal_merge(G1, G2)
compare_merge(minimalGraph, G1, G2)
"""
plt.clf()
plt.subplot(3, 2, 1)
plt.title("Graph 1")
nx.draw(G1, node_size=500, with_labels=True)
plt.subplot(3, 2, 2)
plt.title("Degree Distribution Graph 1")
plt.plot(nx.degree_histogram(G1))
plt.subplot(3, 2, 3)
plt.title("Graph 2")
nx.draw(G2, node_size=500, with_labels=True)
plt.subplot(3, 2, 4)
plt.title("Degree Distribution Graph 2")
plt.plot(nx.degree_histogram(G2))
plt.subplot(3, 2, 5)
plt.title("mergedGraph")
nx.draw(priorityGraph, node_size=500, with_labels=True)
plt.subplot(3, 2, 6)
plt.title("Degree Distribution Merged Graph")
plt.plot(nx.degree_histogram(priorityGraph))
plt.show()
"""