Networks and graphs

Put 1,000 nodes on a ring and link each to its ten nearest neighbors, five on either side: the shortest path between two nodes is then 50.45 links long on average. Rewire 1 % of the 5,000 links to random partners and the average drops to 9.03. A few long links do most of the work. Network analysis asks such questions of any system made of parts and connections: the proteins of a cell and which of them bind, the bonds of a molecule read as a graph, the fractures through which groundwater moves in rock, the lines of a power grid where one failure reroutes the load. People want to know which node matters most, how far apart two nodes are, which groups hang together, and how something spreads.

In Python the standard is NetworkX. nx.Graph and add_edge build a graph, nx.shortest_path_length measures distances, nx.betweenness_centrality ranks nodes by how many shortest paths run through them, and nx.community.louvain_communities finds groups. Generators such as nx.erdos_renyi_graph and nx.watts_strogatz_graph give random graphs to compare against. For graphs with millions of links, scipy.sparse.csgraph runs shortest_path and connected_components on a sparse adjacency matrix. In Julia, Graphs.jl has SimpleGraph, add_edge!, dijkstra_shortest_paths, betweenness_centrality, and connected_components.

Start by building a graph from an edge list or an adjacency matrix and looking at its degree distribution and its shortest paths. Random graph models come next, because they are the null hypothesis: in a random graph of 10,000 nodes with on average two links per node, 80 % of the nodes sit in one connected component, so a large component in your data is no discovery by itself. Communities follow, and processes on networks such as spreading and the synchronization of coupled oscillators come last; what happens on each node is dynamical systems.

What belongs here

Systems described as nodes and links: building graphs from data, degree distributions, shortest paths, centrality, communities, random graph models, and processes on networks such as spreading and synchronization, with NetworkX in Python and Graphs.jl in Julia. Graph algorithms used inside sparse solvers belong to sparse-linear-algebra.