Firsts in network science

This post is revised after comments from Urska Demsar, Travis Gibson, Des Higham, Mason Porter, 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 discipline 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).
  • Papers that are a bit lesser known (sorry Euler).

But please take it all with a grain of salt and lemme know what I forgot.

moreno_early
The first published network illustration by Moreno, 1932.

Network positions

…i.e. the idea that one can learn about the nodes in a network by looking at 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 1930’s. 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.

that I haven’t got the hands on myself, but Linton Freeman writes the following about the figure above:

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”).

Also Jennings was 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 undercredited 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”.

moreno_random
One instance of the random graph model of Moreno & Jennings, 1938. Every node has three outgoing links wired to random other nodes.

Random graphs

…were also first studied by Helen Jennings and Jacob Moreno in

JL Moreno, HH Jennings, 1938. Statistics of social configurations. Sociometry, 1(3/4):342–374.

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.

A honorable mention goes to Solomonoff and Rapoport that invented random graphs independently (still before Erdős-Rényi):

R Solomonoff, A Rapoport, 1951. Connectivity of random nets. Bull. Math. Biophysics 13:107–117.

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 deeper analysis than Solomonoff and Rapoport. Rapoport also had a paper from 1948 studying random configurations of one node with one outgoing link attaching to a random other node.

A Rapoport, 1948. Cycle distributions in random nets. Bull. Math. Biophysics 10(3):145–157.

Network structure

= 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 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 happen in parallel (probably to the tones of Jailhouse Rock and Great Balls of Fire)

L Katz, JH Powell, 1957. Probability distributions of random variables associated with a structure of the sample space of sociometric investigations. Ann. Math. Statist. 28(2):442–448.

HJ Ryser, 1957. Combinatorial properties of matrices of zeros and ones. Canadian J. Math. 9(3):371–377.

D Gale, 1957. A theorem on flows in networks. Pacific J. Math. 7(2):1073–1082.

…all effectively discusses the configuration model (without multiedges). The latter two papers are similar (talking about existence of graphs with given degree sequences—the “graphicality”).

The idea of describing such graphs by matching stubs (and the word “configuration model”) comes from Béla Bollobás’s AFAIK most cited paper:

B. Bollobás, 1980. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin. 1:311–316.

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

EF Connor, D Simberloff, 1979. The assembly of species communities: Chance or competition? Ecology, 60(6):1132–1140.

…but it is for bipartite networks.

moreno_groups
Friendships among 4th graders. Communities split by gender. From: JL Moreno, 1934. Who Shall Survive?

Community structure

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 😦 ).

SA Rice, 1927. The identification of blocs in small political bodies. American Political Science Review, 21(3):619–627.

Community detection as we know it today, entered the stage after conceptually very similar analysis methods. The first one is graph partitioning—to split a graph into two communities. Just repeating graph partitioning is a community detection method—not necessarily good, 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 probably:

BW Kernighan, S Lin, 1970. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal 49:291–307.

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 second method akin to community structure is hierarchical clustering. In this approach one splits (or joins) 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.

Eigenvector centrality

Writing blog posts is the best way of learning! A reader kindly pointed me to a 1895 paper about scoring chess tournaments by eigenvector centrality

E Landau, 1895. Zur relativen Wertbemessung der Turnierresultate. Deutsches Wochenschach 11:366–369.

Note that this was before the Perron-Frobenius theorem.

Distance-based centrality measures

These goes back at least to (above mentioned) ideas of Kurt Lewin. In 1948, Alex Bavelas tried to translate these into a mathematical language.

A Bavelas, 1948. A mathematical model for group structures. Applied Anthropology 7(3):16–30.

Bavelas writes:

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.

holland_leinhard
Triads of four directed edges from Holland & Leinhardt, 1970.

Network motifs

From this recent paper (Network motifs and their origins, by Stone, Simberloff, Artzy-Randrup), 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

PW Holland, S Leinhardt, 1970. A method for detecting structure in sociometric data. Am. J. Sociol. 76(3):492–513.

are very similar in spirit (even though their method is restricted to triangle counts in somewhat restricted sets of graphs).

Node importance via the effect 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

H Corley, H Chang, 1974. Finding the n most vital nodes in a flow network. Management Science 21(3):362–364.

(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 1970’s (I already mentioned Zachary’s karate club paper inspired by the same max-flow/min-cut algorithm).

morris_kretzschmar
Outbreak sizes vs. degree correlation from Morris & Kretzschmar, 1995.

Tuning the structure of a network and measure the response of dynamics

This is what I am least sure of. It seems like such an obvious idea. I can imagine electric engineers did it before, or geographers (often unsung heroes, pioneering many ideas of network/data science decades ago that still feels very fresh). The first paper that to 95% fits the description is by Martina Morris and Mirjam Kretzschmar:

M Morris, M Kretzschmar, 1995. Concurrent partnerships and transmission dynamics in networks. Social Networks 17(3/4):299–318.

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.

Coda

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 good about being a shiny bolt in the great machinery of science.

Postscriptum

I got several comments to this post mentioning forgotten pioneering papers. E.g. works by geographers (whom I do respect super much (as any loyal reader of my blog / twitter posts would know)). 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 an idea that still lingers, but that they broke new ground for such ideas. For example

S Mason, 1953. Feedback theory-some properties of signal flow graphs. Proceedings of the IRE 41(9), 1144–1156.

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 1930’s that, at least as a problem, feel similar to today’s network science.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s