I revised this post after comments from Urska Demsar, Travis Gibson, Des Higham, Mason Porter, Max Schich, Jan Peter Schäfermeyer, Johan Ugander, and Jean-Gabriel Young. Thanks!
Our field is interdisciplinary, and many smart people have been thinking about similar things. No wonder things get reinvented and rediscovered many times. I don’t think science is a competition to get good ideas first. On the other hand, who was the first to come up with this or that is a perfect conversation starter across disciplines . . I know people rooting for their field like a sports team.
Here is a list of some first appearances/applications of some big ideas. I restrict myself to:
- The pre-Watts-Strogatz era.
- Ideas that are in active use today (sorry Euler).
- Omitting networks only used illustrate the connections between different items. (That could be a future blog post.)
But please take it all with a grain of salt and lemme know what I forgot.
…i.e. the idea that one can learn about the nodes in a network by how they are connected to the rest of the network. It is tricky to pinpoint who got the idea first, but the first to implement it and actually collect data were probably by Jacob Moreno and Helen Jennings in the early 1930s. German psychologists of the interwar era—like Kurt Lewin or Otto Selz—often discussed their theories in terms of networks. Possibly this was a source of influence for Moreno and Jennings. But as far as I know, they didn’t actually collect and measure network data. The first publication doing that was:
JL Moreno, 1932. Application of the group method to classification. National Committee on Prisons and Prison Labor, New York.
He characterized that image as showing “a group in which two dominating individuals are strongly united both directly and indirectly through other individuals.” Thus, Moreno viewed that picture as a display of both cohesiveness (“strongly united”) and social roles (“dominating individuals”).
Jennings was also involved in this work. Moreno’s son’s biography of Moreno mentions that Jennings did all the data collection and analysis in all of their network (sociogram) papers. It’s intriguing that network science also had an under-credited female pioneer and tricky to find much information about her online. Moreno’s biography paints a picture of her as a brilliant but sad character “remembered in our family lore as a lonely person.”
…were also first studied by Helen Jennings and Jacob Moreno in
More specifically, they consider a model where n directed degrees per node were attached to random other nodes and studied the fraction of reciprocated links in their network data compared to the random model.
This paper derives the phase transition of the giant component and builds a mathematical theory (that Moreno and Jennings never did). Of course, Erdős and Rényi made a yet more in-depth analysis than Solomonoff and Rapoport. Rapoport also had a paper from 1948 studying random configurations of where nodes have only one outgoing link attaching to a random other node.
= the way a network differs from a random null model. This must also be attributed to Moreno & Jennings (their 1938 paper above uses random graphs as null models to define the structure, e.g., the tendency for social ties to be reciprocated).
Random graphs with given degrees
(I.e., more or less the configuration-model). They were around before Molloy and Reed’s work on the giant component. As so often happens, this invention seems to have occurred in parallel (probably to the tones of Jailhouse Rock and Great Balls of Fire)
…all effectively discusses the configuration model (without multiedges). The last two papers are similar (talking about the existence of graphs with given degree sequences—the “graphicality”).
The idea of describing such graphs by matching stubs, and the name “configuration model,” comes from Béla Bollobás’s AFAIK most cited paper:
Rewiring edges for network null models
This is related to the previous item because early netsci papers typically constructed random networks with the same degree sequence as an empirical one by randomly rewiring them. The first such paper I know of is
…but it is for bipartite networks.
This is tricky. First, even Moreno and Jennings talked about cohesive groups in the context of their study of school children. But they never gave a formal definition (let alone proposed an algorithm to detect them). Even earlier, in the context of analyzing voting patterns, Rice proposed a method of identifying political blocs by examining the network of agreements/disagreements (but no network visualization 😦 ).
Community detection, as we know it today, entered the stage after conceptually very similar analysis methods.
The second method is graph partitioning—splitting a graph into two communities. Just repeating graph partitioning is a community detection method—not necessarily excellent, but probably better than the worst (and actually what karate-club Zachary did in his karate-club paper). The starting point of graph partitioning algorithms was perhaps:
The problem itself seems to have been around some time by then since it was also the topic of Kernighan’s Ph.D. thesis.
The third method akin to community structure is hierarchical clustering. In this approach, one splits (or joins) a group of stuff based on some connection strength between pairs of them. It was, for many years, not directly applied to finding clusters of graphs. The first such method was the CONCOR algorithm:
RL Breiger, S Boorman, P Arabie, 1975. An algorithm for clustering relational data with applications to social network analysis and comparison with multidimensional scaling. J. Math. Psychol. 12:328–383.
That came out of the interest in block models of social networks pioneered by Harrison White and colleagues.
Writing blog posts is the best way of learning! A reader kindly pointed me to an 1895 paper about scoring chess tournaments by eigenvector centrality
Note that this was before the Perron-Frobenius theorem.
Distance-based centrality measures
These go back at least to (the above-mentioned) ideas of Kurt Lewin. In 1948, Alex Bavelas tried to translate these into a mathematical language.
The central region of a structure is the class of all cells with the smallest [longest distance] to be found in the structure.
I.e., the inverse eccentricity. It also mentions the importance of being central in rumor propagation.
From this recent paper (Network motifs and their origins, by Stone, Simberloff, Artzy-Randrup), which I read just a few days ago (that prompted me to write this blog post), I learned that network motifs were first proposed in the Ph.D. thesis of Lewis Stone, 1988. Although I have to say precursors like
are very similar in spirit (even though their method is restricted to triangle counts in somewhat restricted sets of graphs).
Node importance via the impact of their deletion
This is an idea that has been (re)invented maybe more than any other. To evaluate the importance of a node by checking what happens to the system if it is deleted. To the best of my knowledge, the first paper with this idea is
(A top journal in the field of management science! Not the usual place to look for groundbreaking network science (anymore).) Where they look at what happens to maximal flows when nodes are deleted. The influence of the invention of the Ford–Fulkerson algorithm was immense in the 1970s (I already mentioned Zachary’s karate club paper inspired by the same max-flow/min-cut algorithm).
Correlating network structural measures with a quantity of interest
The first doing this fairly fundamental network science analysis that I know about was KJ Kansky in his Ph.D. thesis The structure of transportation networks. Kansky showed how the densitiy of countries’ railroad neworks predicted imports.
Tuning the structure of a network and measuring the response of dynamics
Related to the previous topic it seems like an obvious idea measure the response of a quantity of interest to a property that could be tuned in a network model. I can imagine electrical engineers did it before, or geographers (often unsung heroes, pioneering many approaches of network/data science decades ago that still feel very fresh). The first paper that—to 95%—fits the description is by Martina Morris and Mirjam Kretzschmar:
It is 95%, not 100% because they don’t generate the (temporal) networks explicitly, and never measure the network structure netsci-style. They do it alongside the disease simulation and control the structure by imposing it in their generative model.
For the tongue-in-cheek competition between disciplines, I note that psychology, mathematics, and sociology are doing well in getting my mentions. More interesting, however, are the many cases of simultaneous inventions—like the three papers 1957 all proposing the configuration model or the 1975 publications of the defining works of graph partitioning and hierarchical clustering of networks. Judging from these observations, it is probably better to credit the ideas to the field, rather than individuals. I will (at least for today) forget my Einstein ambitions and feel right about being a shiny bolt in the vast machinery of science.
I got several comments on this post, mentioning forgotten pioneering papers. E.g., works by geographers and urban planners (whom I do respect super much (as any loyal reader of my blog/twitter posts would know)). I added a beautiful example of network arguments in geography above. This post is about the core ideas of network science (defined roughly as the science of people who feel at home at the NetSci conferences series). The legacy of many of these early papers is not that they introduced ideas that still linger, but that they broke new ground that eventually leads to modern network science. For example
that points out how radically different directed acyclic graphs are from graphs with cycles and the impact of self-links. Also, the theory of transport networks had remarkably early papers such as AN Tolstoy’s 1930 paper about minimizing the transportation costs in railway systems. Similarly, power engineering had methods to simplify circuit diagrams in the 1930s that, at least as a problem, feel similar to today’s network science.