This page provides some useful resources about NetworkX — a very useful python libary for manipulating and analyzing graphs.
Brief intro to NetworkX:
NetworkX is a well maintained Python library for the creation, manipulation, and study of graphs and complex networks. NetworkX provides data structures for networks along with graph algorithms, generators, and drawing tools. In particular NetworkX complements Python’s scientific computing suite of SciPy/NumPy, Matplotlib, and Graphviz and can handle graphs in very large memory. NetworkX is recommended to be part of every data scientist’s toolkit.
The core algorithms that are included are implemented on very fast legacy code. Graphs are hugely flexible (nodes can be any hashable type), and there is an extensive set of native IO formats.
-
- NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks.
- Github repo — Website page — Documentation — Reference »Glossary
Algorithms and Functions in NetworkX:
https://stackoverflow.com/questions/28966239/python-networkx-bridge-detection
- Python Networkx detecting loops/circles
https://stackoverflow.com/questions/35683302/python-networkx-detecting-loops-circles
- TBA
- TBA
Graph Generators in NetworkX (Reference » Graph generators):
Notes
Graph, node, and edge data are not propagated to the new graph. For undirected graphs, the nodes in G must be sortable, otherwise the constructed line graph may not be correct.
Self-loops in undirected graphs
For an undirected graph G
without multiple edges, each edge can be written as a set {u, v}
. Its line graph L
has the edges of G
as its nodes. If x
and y
are two nodes in L
, then {x, y}
is an edge in L
if and only if the intersection of x
and y
is nonempty. Thus, the set of all edges is determined by the set of all pairwise intersections of edges in G
.
Trivially, every edge in G would have a nonzero intersection with itself, and so every node in L
should have a self-loop. This is not so interesting, and the original context of line graphs was with simple graphs, which had no self-loops or multiple edges. The line graph was also meant to be a simple graph and thus, self-loops in L
are not part of the standard definition of a line graph. In a pairwise intersection matrix, this is analogous to excluding the diagonal entries from the line graph definition.
Self-loops and multiple edges in G
add nodes to L
in a natural way, and do not require any fundamental changes to the definition. It might be argued that the self-loops we excluded before should now be included. However, the self-loops are still “trivial” in some sense and thus, are usually excluded.
Self-loops in directed graphs
For a directed graph G
without multiple edges, each edge can be written as a tuple (u, v)
. Its line graph L
has the edges of G
as its nodes. If x
and y
are two nodes in L
, then (x, y)
is an edge in L
if and only if the tail of x
matches the head of y
, for example, if x
and
= (a, b)y = (b, c)
for some vertices a
, b
, and c
in G
.
Due to the directed nature of the edges, it is no longer the case that every edge in G
should have a self-loop in L
. Now, the only time self-loops arise is if a node in G
itself has a self-loop. So such self-loops are no longer “trivial” but instead, represent essential features of the topology of G
. For this reason, the historical development of line digraphs is such that self-loops are included. When the graph G
has multiple edges, once again only superficial changes are required to the definition.
References
-
-
- Harary, Frank, and Norman, Robert Z., “Some properties of line digraphs”, Rend. Circ. Mat. Palermo, II. Ser. 9 (1960), 161–168.
- Hemminger, R. L.; Beineke, L. W. (1978), “Line graphs and line digraphs”, in Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory, Academic Press Inc., pp. 271–305.
-
NetworkX Tutorials:
- Examples and IPython Notebooks about NetworkX (official tutorials)
- Complex network analysis using NetworkX – Graph Theory in Python (Notebooks used at SciPy India 2015 and VPCOE (University of Pune) tutorials on NetworkX)
- Exploring and Analyzing Network Data with Python — PDF — (moreNetwork analysis tutorials on Programming Historian site)
- NetworkX: Network Analysis with Python — PDF
- An Introduction to Graph Theory and Network Analysis (with Python codes) — the link to the dataset
- NetworkX tutorials
- PyViz tutorial (06 Network Graphs)
- Graph Optimization with NetworkX in Python (September 12th, 2017 by Andrew Brooks) — PDF
Galil, Z. (1986). “Efficient algorithms for finding maximum matching in graphs“. ACM Computing Surveys. Vol. 18, No. 1: 23-38.
Packages built on NetworkX
multiNetX is a python package for the manipulation and visualization of multilayer networks. It is build on NetworkX . The core of this package is a MultilayerGraph, a class that inherits all properties from networkx.Graph().
This allows for:
-
-
- Creating networks with weighted or unweighted links (only undirected networks are supported in this version)
- Analysing the spectral properties of adjacency or Laplacian matrices
- Visualizing dynamical processes by coloring the nodes and links accordingly
-
- TBA
References:
To cite NetworkX please use the following publication:
Aric A. Hagberg, Daniel A. Schult and Pieter J. Swart, “Exploring network structure, dynamics, and function using NetworkX”, in Proceedings of the 7th Python in Science Conference (SciPy2008), Gäel Varoquaux, Travis Vaught, and Jarrod Millman (Eds), (Pasadena, CA USA), pp. 11–15, Aug 2008