Simply put: A graph is a way of specifying relationships amongst a collection of objects.
Graphs are everywhere...
Can yo u think of an example?
In [1]:
# Config environment for code examples.
%matplotlib inline
import networkx as nx
import matplotlib as plt
plt.rcParams['figure.figsize'] = 12, 7
In [2]:
g = nx.scale_free_graph(10)
nx.draw_networkx(g)
Graphs can be thought about as a collection of unique nodes and edges.
For example, in a social network a node is an indivdual.
An edge would be the relationship between two individuals, often containing semantic information about that relationship.
A dyad is the fundamental unit in social network analysis:
So if a dyad is two nodes and an edge, what's a triad?
In [3]:
g = nx.Graph([(1, 2), (1, 3), (2, 3)]) # networkx.Graph accepts an edge list as an init param.
nx.draw_networkx(g)
A triangle is a complete graph.
Hint: if you don't use itertools yet, it's time that you start.
In [4]:
def complete_graph(num_nodes):
"""
:param num_nodes: number of nodes to include in the complete graph.
:returns: networkx.Graph. a complete graph.
"""
pass # Get rid of this pass statement.
Modes: 1-mode vs. 2-mode/bimodal/bipartite vs. multimodal/multipartite
Directed vs. undirected
Multigraph
In [5]:
print(nx.Graph, nx.DiGraph, nx.MultiGraph, nx.MultiDiGraph)
Whoaaa there! Let's slow down and think about different ways of storing graph data.
In [6]:
g = nx.gnp_random_graph(10, 0.5) # Random graph generator.
In [7]:
nx.to_numpy_matrix(g)
Out[7]:
In [8]:
g.edges()
Out[8]:
You read the chapters right? So what is an adjacency list?
Here's a hint:
In [9]:
g.adj
Out[9]:
Yes, but there's more...
What about node attributes?
In [10]:
g.node # Dict containing node attributes.
Out[10]:
Hmmm...see all those empty dict objects?
In [11]:
g.node[0]["type"] = "person"
g.node[0]["name"] = "ryu"
In [12]:
g.nodes(data=True)
Out[12]:
In [13]:
g.node[0]
Out[13]:
So that was node access, edge access is like whaaaa?
In [14]:
# Well watch this...
g.adj[0]
Out[14]:
In [15]:
# And this...
g[0]
Out[15]:
In [16]:
# And this...
g.edge[0]
Out[16]:
WARNING Setting attributes on the edge API can be risky if you don't know what you are doing. We will discuss this in a future challenge.
NetworkX provides a wide variety of data structures, methods, and functions for interacting with graphs!
One of the fundamental concepts in graph theory is the traversal.
<img="Depth-first-tree.svg" />
In [17]:
# This is the starting graph.
nx.draw_networkx(g)
In [18]:
depth_first_traversal = list(nx.dfs_edges(g, 3))
print(depth_first_traversal)
In [19]:
nx.draw_networkx(nx.Graph(depth_first_traversal))
In [20]:
breadth_first_traversal = list(nx.bfs_edges(g, 3))
nx.draw_networkx(nx.Graph(breadth_first_traversal))
First look back to the original graph, and think about the implementation of a depth-first vs. breadth-first search.
The dfs_edges and bfs_edges functions return a list of edges representing the walk of the traversal.
In [21]:
g = nx.gnp_random_graph(10, 0.2)
nx.draw_networkx(g)
A graph is connected if for every pair of nodes there is a path between them.
Graphs can have multiple, disconnected components.
A giant component is a component the contains a signifigant fraction of all nodes in the network.
It is highly unlikely that more than one giant component exist.
Write a function "find_neighbors" that accepts the parameters (graph, node, distance) where graph is an networkx.Graph, node is the start node and distance is the number of steps to walk, that walks the graph, starting at the start node, to a specified distance away from the start node returning all of the neighbors found on the walk as a set. For example, if I call:
find_neighbors(graph, "johnny", 2)
It will return all of johnny's neighbors at a distance of two, meaning the neighbors of his neighbors (the friends of his friends).
THIS IS A HARD CHALLENGE WITH MULTIPLE VALID SOLUTIONS. GOOD LUCK!!!
In [22]:
# Remember
g = nx.gnp_random_graph(10, 0.5)
g[0] # Returns edges (neighbors).
Out[22]:
In [23]:
g.neighbors(0) # Also returns neighbors.
Out[23]:
In [24]:
set(g[0]) # Returns a set of neighbors.
Out[24]:
In [25]:
# Here's a template:
def find_neighbors(graph, node, distance):
"""
:param graph: networkx.Graph
:param node: a node in the graph.
:param distance: an integer specifying the max distance of the walk.
:returns: A set of neighbors returned by the walk.
"""
pass # Get rid of this pass statement.