Real-World Networks#
The term real-world networks describes graphs that are the direct representation of a relation existing in the real world. Examples are friendships between persons (social network), collaborations between researchers (collaboration network), roads between intersections (road networks), cables between autonomous systems forming the internet (technical networks), or interactions between proteins (biological networks).
Problem Instances#
Real-world networks are an important type of input for many graph problems. A nice collection of networks used in [1 On the External Validity of Average-case Analyses of Graph Algorithms (2023) ] can be found on Zenodo [2 almost 3000 Networks (unweighted, undirected, simple, connected) from Network Repository (2023) ]. Additional networks are available via Network Repository, KONECT, and SNAP.
Limitations#
Graph algorithms have applications that go beyond computing some property on a real-world network. In these cases, the input graph is often some kind of auxiliary graph, which might have very different properties than typical real-world networks.
It clearly depends on the specific problem whether real-world networks can be seen as “practical inputs”. While computing the diameter is important when studying real-world networks, computing a large independent set is probably more relevant for auxiliary graphs modeling some kind of conflicts (e.g., when computing a maximum number of non-overlapping labels on a map).
While a large collection of real-world networks is readily available, the situation is less stellar for other types of inputs. We should probably try to change that.