Assyrian merchants meet nuclear physicists: history of the early contributions from social sciences to computer science. The case of automatic pattern detection in graphs (1950s–1970s)

ABSTRACT

Community detection is a major issue in network analysis. This paper combines a socio-historical approach with an experimental reconstruction of programs to investigate the early automation of clique detection algorithms, which remains one of the unsolved NP-complete problems today. The research led by the archaeologist Jean-Claude Gardin from the 1950s on non-numerical information and graph analysis is retraced to demonstrate the early contributions of social sciences and humanities. The limited recognition and reception of Gardin's innovative computer application to the humanities are addressed through two factors, in addition to the effects of historiography and bibliographies on the recording, discoverability, and reuse of scientific productions: (1) funding policies, evidenced by the transfer of research effort on graph applications from temporary interdisciplinary spaces to disciplinary organizations related to the then-emerging field of computer science; and (2) the erratic careers of algorithms, in which efficiency, flaws, corrections, and authors' status, were determining factors.

KEYWORDS:

• History of computing
• clique detection
• community detection
• social networks
• sociometry
• graph analysis
• algorithm

Acknowledgments

I thank Pierre-Éric Mounier-Kuhn for his advice and providing me with the archives of the Institut Blaise Pascal, Solène Chevalier for her help in accessing some documents and Alain Guénoche for his support in understanding Jaulin's algorithm.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 Many of these methods rely on the optimization of modularity (Newman and Girvan 2004).

2 See also Lankford (1974) for a review of detection methods where ‘clique’ means ‘community’.

3 For a detailed account of these data, see Plutniak (2018, 7–11).

4 ‘Comité de direction. Réunion du 16 mars 1961’, 16-03-1961, JCG 1, Mae.

5 Gardin and Garelli (1961, 847). However, in the ‘Séminaire sur les modèles mathématiques dans les sciences sociales’, Gardin mentioned ‘about’ 3000 names (Gardin 1961, 23) and, in the later republication of the Annales article in English, the number of 20,000 is given (Gardin 1965a, 380).

6 Gardin (1961, 25). The authors expected that subsequent analyses would have to cover about 100 names (Gardin and Garelli 1961, 876, Gardin (1962a, 457)). In a later commentary, Gardin mentions calculations made on a square matrix corresponding to the relationships among 200 merchants (Gardin 1965c, 389).

7 For a detailed bibliographic study of its reception, see Plutniak (2018, 30–37).

8 Archives consulted: Jean-Claude Gardin's files at the Maison Archéologie-Ethnologie, Paris X University, Nanterre, France (hereafter abbreviated Mae); Euratom files of the Historical archives of the European Commission, in Fiesole, Italy (Haeu) ; Cada files at the Cepam archaeology laboratory, Nice, France (Cepam); files of the Institut Blaise Pascal, private files of Pierre-Éric Mounier-Kuhn (Ibp).

9 For a detailed description, see Plutniak (2018, 11–14).

10 As testified by the 22 contracts listed in Meyer-Uhlenried, Karl-Heinrich, ‘Organization de la collaboration entre la Commission et les institutions scientifiques des pays de la Communauté pour l’élaboration d'un langage documentaire (principe des contrats)', 15 January 1960, BAC-059-1980 0209, Haeu.

11 Broadly understood to include physio-psychology.

12 Contract 001-60-1 CETF from the 10 March 1960.

13 ‘Contrat de recherche entre la Communauté européenne de l’énergie atomique et l'Association Marc Bloch', 21 December 1959, BAC-118-1986 1442, Haeu.

14 Equivalent purchasing power in euros in 2017, taking into account monetary erosion due to inflation, calculated using the Insee converter (https://insee.fr/fr/information/2417794).

15 Gardin J.-C., ‘Programme d’études sémiologiques et documentaire (1961–1965)', October 1960, box Gardin 6, Cepam, p. 3.

16 ‘Travaux du CETIS’, p. 8–9, 28 November 1960, BAC-118-1986 1431, Haeu.

17 See the description of the variables in Gardin and Garelli (1961, 848–850).

18 Acquired in 1957 (Halleux and Xhayet 2007, 159).

19 This teaching took place from 15 to 22 February 1960. Non-numerical information was one of the topic discussed, as illustrated by J. Poyen's presentation ‘Quelques problèmes posés par le traitement de l'information non numérique’.

20 The symposium took place from 24 to 27 April 1961, AAC 117, Mae.

21 Gardin, J.-C., ‘Propositions pour un enseignement sur l'automatique non-numérique (1962)’, 1961, box Gardin 6, Cepam.

22 During WWII, Schützenberger participated in the French Resistance as Gardin, joining London in 1943.

23 ‘Rapport GRISA’, no. 2, May 1960, CEAB12-640, Haeu.

24 From the chapter on Ihm's activities in ‘Travaux du CETIS’, 28-11-1960, BAC-118-1986 1431, Haeu.

25 ‘Réunion du comité scientifique et technique du 14-3-1961. Progrès de l'automatique appliquée au domaine du traitement des informations’, 20-02-1961, BAC-118-1986 1431, Haeu.

26 ‘Orientation des travaux à partir du 2e semestre 1962’, June 1962, box Gardin 6, Cepam, p. 3.

27 NSF (1959, 121).

28 As is often the case, very little information is available about subaltern research workers.

29 Lagrange and Renaud. 1965. Étude d'un réseau sociologique aux Nouvelles-Hébrides, sur calculateur, 55 p., mentioned in Gardin (1965b).

30 Contract between the Sad and the Dgrst n^r 64 FR 175. See also: Sad, ‘Rapport d'activités situation 1963–1964’, 6 March 1964, box Gardin 6, Cepam.

31 Muysers D., Projet d'un langage de programmation numérique et non numérique, adapté plus particulièrement au traitement des données structurées par réseau. Report to the Dgrst, April 1966, JCG 156, Mae.

32 Perrot J., Berstel, J.-F. 1967. Rapport final de la Convention de Recherche DGRST 65 FR 002, ‘Contrat Graphes’, mimeograph, Institut de Programmation.

33 See Plutniak (2018, 26–30).

34 The same year a programmatic use of algebra to determine cliques was also published, although with no detailed procedure (Festinger 1949, 156).

35 For a review, see Lankford (1974).

36 Later published as Gardin and Jaulin (1968).

37 For a history of this centre, see Nofre (2014).

38 It is indexed but absent in the Mae archives, and not conserved in the Cepam and Haeu archives

39 Cetis, Travaux du CETIS, 28 November 1960, BAC-118-1986 1431, Haeu.

40 Cnrs, ‘Centre d'analyse documentaire pour l'archéologie’ in Rapport d'activité. Octobre 1961–Octobre 1962, p. 417.

41 The algorithms used included: Bron and Kerbosch (1973), implemented in the maxClique() function from the RBGL package; Östergård (2001), qpGetCliques(), qpgraph package; Makino and Uno (2004): clique.census() function, sna package; and Eppstein, Löffler, and Strash (2010), max_cliques() function, igraph package. See supplementary materials.

42 Later literature reviews do not mention Jaulin's method, even those published in French, e.g. Schneider (1973).

Additional information

Notes on contributors

Sébastien Plutniak

Sébastien Plutniak (M.A. in archaeology, PhD in sociology, Ehess – School for Advanced Studies in the Social Sciences, France) is a sociologist and prehistoric archaeologist, former fellow of the École française de Rome. His research interests revolve around the use of formal and computer-based methods in the humanities and social sciences, from a socio-historical and epistemological perspectives. Archaeology during the second half of the 20th century is used as his main case study, while also being interested in applying formal methods to a wide range of research topics from bibliometry in science studies to social network analysis in ethnography.