Tutorial¶
This guide can help you start working with IntervalGraph module of DyNetworkX.
Disclaimer: this tutorial, similar to DyNetworkX itself, is heavily influenced by NetworkX’s tutorial. This is done on purpose, in order to point out the similarities between the two packages.
Creating an interval graph¶
Create an empty interval graph with no nodes and no edges.
>>> import dynetworkx as dnx
>>> IG = dnx.IntervalGraph()
By definition, an IntervalGraph
is a collection of nodes (vertices) along with
identified pairs of nodes (called interval edges, edges, links, etc) each of which is
coupled with a given interval. In DyNetworkX, just like NetworkX, nodes can be any
hashable object e.g., a text string, an image, an XML object, another Graph,
a customized node object, etc.
Note
Python’s None
object should not be used as a node as it determines
whether optional function arguments have been assigned in many functions.
Nodes¶
Using DyNetworkX’s IntervalGraph.load_from_txt()
method, the graph
IG
can be grown by importing an existing network. However, we first
look at simple ways to manipulate an interval graph. The simplest
form is adding a single node,
>>> IG.add_node(1)
add a list of nodes,
>>> IG.add_nodes_from([2, 3])
or add any iterable container of nodes. You can also add nodes along with node attributes if your container yields 2-tuples (node, node_attribute_dict). Node attributes are discussed further below.
>>> H = dnx.IntervalGraph()
>>> IG.add_node(H)
Note that interval graph IG
now contains interval graph H
as a node.
This flexibility is very powerful as it allows graphs of graphs, graphs
of files, graphs of functions and much more. It is worth thinking
about how to structure your application so that the nodes are
useful entities. Of course you can always use a unique
identifier in IG
and have a separate dictionary
keyed by identifier to the node information if
you prefer.
Note
You should not change the node object if the hash depends on its contents.
Edges¶
Edges are what make an interval graph possible. Every edge is defined by 2 nodes, the inclusive beginning of the interval when the edge first appears and its non-inclusive end. Beginning of an interval must be strictly smaller than its end and both can be of any orderable types.
Note
In this tutotial as well as IntervalGraph documentation, the two terms edge
and interval edge
are used interchangeably.
IG
can also be grown by adding one edge at a time,
>>> IG.add_edge(1, 2, 1, 4) # n1, n2, beginning, end of the edge interval
>>> ie = (2, 3, 2, 5)
>>> IG.add_edge(*ie) # unpack interval edge tuple*
by adding a list of edges,
>>> IG.add_edges_from([(1, 2, 2, 6), (1, 3, 6, 9)])
or by adding any ebunch of edges. An ebunch is any iterable container of interval edge-tuples. An interval edge-tuple is a 4-tuple of nodes and intervals.
Note
In above example it is worth noting that the two added interval edges,
(1, 2, 1, 4)
and (1, 2, 2, 6)
are two different interval edges,
since they exists on different intervals.
If a new interval edge is to be added with nodes that are not currently in the interval graph, nodes will be added automatically.
There are no complaints when adding existing nodes or edges. As we add new nodes/edges, DyNetworkX quietly ignores any that are already present.
>>> IG.add_edge(1, 2, 1, 4)
>>> IG.add_node(1)
At this stage the interval graph IG
consist of 4 nodes and 4 edges,
>>> IG.number_of_nodes()
4
>>> len(IG.edges())
4
We can examine nodes and edges with two interval graph methods which facilitate reporting:
IntervalGraph.nodes()
and IntervalGraph.edges()
. These are lists
of the nodes and interval edges. They offer a continually updated read-only view
into the graph structure.
>>> IG.nodes()
[1, 2, 3, <dynetworkx.classes.intervalgraph.IntervalGraph object at 0x100000000>]
IG.edges()
is an extremely flexible and useful method to query the interval
graph for various interval edges. It returns a list of Interval objects which
are in the form Interval(begin, end, (node_1, node_2)
.
Using this method you have access to 4 constraints in order to restrict your query. u, v, begin and end. Defining any of them narrows down your query.
>>> IG.edges() # returns a list of all edges
[Interval(6, 9, (1, 3)), Interval(2, 5, (2, 3)), Interval(2, 6, (1, 2)), Interval(1, 4, (1, 2))]
>>> IG.edges(begin=5) # all edges which have an overlapping interval with interval [5, end of the interval graph]
[Interval(6, 9, (1, 3)), Interval(2, 6, (1, 2))]
>>> IG.edges(end=3) # all edges which have an overlapping interval with interval [beginning of the interval graph, 3)
[Interval(2, 5, (2, 3)), Interval(2, 6, (1, 2)), Interval(1, 4, (1, 2))]
>>> IG.edges(u=1, v=2) # all edge between nodes 1 and 2
[Interval(2, 6, (1, 2)), Interval(1, 4, (1, 2))]
>>> IG.edges(1, 2, 5, 6) # all edges between nodes 1 and 2 which have an overlapping interval with [5, 6)
[Interval(2, 6, (1, 2))]
One can also take advantage of this method to obtain more information such as degree. Since in an interval graph these parameters change depending on the interval in question, you need to adjust your query.
Accessing degree of a node:
>>> len(IG.edges(u=1)) # total number of edges associated with node 1 over the entire interval
3
>>> len(IG.edges(u=1, begin=2, end=4)) # Adding interval restriction
2
Keep in mind that end
is non-inclusive. Thus, depening on what time increment you use
to define your interval, if you set end = begin + smallest_increment
it will
return all the edges which are present at time begin
.
>>> len(IG.edges(u=1, begin=5, end=6))
1
If you are using a truly continuous time interval, you can add your machine epsilon to
begin
to achieve the same result. As an example:
>>> import numpy as np
>>> eps = np.finfo(np.float64).eps
>>> begin = 5
>>> IG.edges(u=1, begin=begin, end=begin + eps)
[Interval(2, 6, (1, 2))]
As it is shown, IG.edges()
is a powerful method to query the network for edges.
You can also take advantage of IntervalGraph.has_node()
and
IntervalGraph.has_edge()
as it is shown below,
>>> IG.has_node(3)
True
>>> 1 in IG # this is equivalent to IG.has_node(1)
True
>>> IG.has_node(5)
False
>>> IG.has_edge(2, 3)
True
>>> IG.has_edge(1, H)
False
Or constraint the begin and/or end of your search:
>>> IG.has_node(3, end=2) # end is non-inclusive
False
>>> IG.has_edge(2, 3, 3, 7) # matching an interval edge with nodes 2 and 3, and overlapping interval [3, 7)
True
>>> IG.has_edge(2, 3, 3, 7, overlapping=False) # setting overlapping=False, searches for an exact interval match
False
One can remove nodes and edges from the graph in a similar fashion to adding.
by using IntervalGraph.remove_node()
and
IntervalGraph.remove_edge()
, e.g.
>>> IG.remove_node(H)
[1, 2, 3]
>>> IG.remove_edge(1, 3, 6, 9, overlapping=False)
>>> IG.edges()
[Interval(2, 5, (2, 3)), Interval(2, 6, (1, 2)), Interval(1, 4, (1, 2))]
What to use as nodes and edges¶
Just like NetworkX, DyNetworkX does not have a specific type for nodes an edges.
This allows you to represent nodes and edges with any hashable object to add
more depth and meanning to your interval graph. The most common choices are
numbers or strings, but a node can be any hashable object (except None
),
and an edge can be associated with any object x
using
IG.add_edge(n1, n2, begin, end, object=x)
.
As an example, n1
and n2
could be real people’s profile url or a
custom python object and x
can be another python object which
describes the detail of their contact. This way, you are not
bound to only associating weights with the edges.
Based on the NetworkX’s experience, this is quite useful, but its abuse can lead to unexpected surprises unless one is familiar with Python.
Adding attributes to graphs, nodes, and edges¶
Attributes such as weights, labels, colors, or whatever Python object you like, can be attached to graphs, nodes, or edges.
Each graph, node, and edge can hold key/value attribute pairs in an associated
attribute dictionary (the keys must be hashable). By default these are empty,
but attributes can be added or changed using add_edge
, add_node
.
Graph attributes¶
Assign graph attributes when creating a new graph,
>>> IG = dnx.IntervalGraph(state='Ohio')
>>> IG.graph
{'state': 'Ohio'}
Or you can modify attributes later,
>>> IG.graph['state'] = 'Michigan'
>>> IG.graph
{'state': 'Michigan'}
There is also an spacial attribute for interval graphs called name
. You
can either set it just like any other attribute or you can take advantage
of the IG.name
property:
>>> IG.name = "USA"
>>> IG.name
USA
Node attributes¶
Add node attributes using add_node()
or add_nodes_from()
,
>>> IG.add_node(1, time='5pm', day="Friday") # Adds node 1 and sets its two attributes
>>> IG.add_nodes_from([2, 3], time='2pm') # Adds nodes 2 and 3 and sets both of their 'time' attributes to '2pm'
>>> IG.add_node(1, time='10pm') # Updates node 1's 'time' attribute to '10pm'
Note that you can update a node’s attribute by adding the node and setting a new value for its attribute.
Edge attributes¶
Similarly, add/change edge attributes using add_edge()
or add_edges_from()
,
>>> G.add_edge(1, 2, 4, 6, contact_type='call') # Adds the edge and sets its 'contact_type' attribute.
>>> G.add_edges_from([(3, 4, 1, 5), (1, 2, 4, 6)], weight=5.8)
>>> G.add_edge(1, 2, 4, 6, weight=6.6) # Updates the weight attribute of the edge.
Note that updating an edge’s attribute is similar to updating nodes’ attributes.
Subgraphs and snapshots¶
You can create one, or a series of snapshots of, NetworkX Graph or MultiGraph from an interval graph if you wish to analyze a portion, or your entire interval graph, using well-known static network algorithms that are available in NetworkX.
Subgraphs¶
To extract a portion of an interval graph, given an interval,
you can utilize IntervalGraph.to_subgraph()
,
>>> IG = dnx.IntervalGraph()
>>> IG.add_edges_from([(1, 2, 3, 10), (2, 4, 1, 11), (6, 4, 12, 19), (2, 4, 8, 15)])
>>> H = IG.to_subgraph(4, 12)
>>> type(H)
<class 'networkx.classes.graph.Graph'>
>>> list(H.edges(data=True))
[(1, 2, {}), (2, 4, {})]
Note that you can also use IntervalGraph.interval()
to get the interval for the
entire interval graph, and use that to convert an interval graph to a NetworkX Graph.
You can also keep the information about each edge’s interval as attributes on the NetworkX’s Graph:
>>> H = G.to_subgraph(4, 12, edge_interval_data=True)
>>> type(H)
<class 'networkx.classes.graph.Graph'>
>>> list(H.edges(data=True))
[(1, 2, {'end': 10, 'begin': 3}), (2, 4, {'end': 15, 'begin': 8})]
Notice that if there are multiple edges available between two nodes, the interval information is going to reflect only one of the edges. Another option is to retrieve a MultiGraph to lose less information in the conversion process:
>>> M = G.to_subgraph(4, 12, multigraph=True, edge_interval_data=True)
>>> type(M)
<class 'networkx.classes.multigraph.MultiGraph'>
>>> list(M.edges(data=True))
[(1, 2, {'end': 10, 'begin': 3}), (2, 4, {'end': 11, 'begin': 1}), (2, 4, {'end': 15, 'begin': 8})]
Snapshots¶
A more traditional method of analyzing continuous dynamic networks has been dividing the network into a series of fixed-interval snapshots. Although some information will be lost in the conversion due to the classic limitations of representing a continuous network in a discrete format, you will gain access to numerous well-defined algorithms which do not exist for continuous networks.
To do so, you can simply use IntervalGraph.to_snapshots()
and set the number of
snapshots you wish to divided the network into:
>>> S, l = G.to_snapshots(2, edge_interval_data=True, return_length=True)
>>> S # a list of NetworkX Graphs
[<networkx.classes.graph.Graph object at 0x100000>, <networkx.classes.graph.Graph object at 0x150d00>]
>>> l # length of the interval of a single snapshot
9.0
>>> for g in S:
>>> ... g.edges(data=True))
[(1, 2, {'begin': 3, 'end': 10}), (2, 4, {'begin': 8, 'end': 15})]
[(2, 4, {'begin': 8, 'end': 15}), (4, 6, {'begin': 12, 'end': 19})]
Combining this method with SnapshotGraph
can be a powerful tool to gain access
to all the methods available through DyNetworkX’s SnapshotGraph
.
Similar to to_subgraph method, you can also divide the interval graph into a series of NetworkX’s MultiGraph, if that is what you need.
Importing from text file¶
Using load_from_txt you can also read in an IntervalGraph or ImpulseGraph
from a text file in a specific edge-list format. For more detail checkout the documentation on
IntervalGraph.load_from_txt()
.
Saving to text file¶
Using save_to_txt you can also write an IntervalGraph or ImpulseGraph
to a text file in a specific edge-list format. For more detail checkout the documentation on
IntervalGraph.save_to_txt()
.