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)
Restricted accessResearch articleFirst published online December, 2021
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)
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.
ArsacJacques.1988. “Des ordinateurs à l'informatique (1952–1972).” In
L'histoire de l'informatique en France, edited by Philippe Chatelin, Vol. 1, 31–43. Grenoble: Institut national polytechnique de Grenoble.
2.
BarthélemyJean-Pierre, and GuénocheAlain. 1988. Les arbres et les représentations des proximités. Méthode + programmes 28. Paris and Milan and Barcelone: Masson.
3.
BeumCorlin O., and BrundageEverett G.. 1950. “A Method for Analyzing the Sociomatrix. ” Sociometry 13 (2): 141–145.
4.
BraffortPaul.1968. L'intelligence artificielle. La Science Vivante. Paris: Presses universitaires de France.
5.
BraffortPaul, and GazzanoAdriano. 1961. “Le calcul électronique à Euratom. ” L'onde électrique 16 (406): 54–56.
6.
BronCoenraad, and KerboschJoep. 1973. “Finding All Cliques of an Undirected Graph (algorithm 457). ” Communications of the ACM 16 (9): 575–576.
7.
ColemanJames S., and MacRaeDuncan. 1960. “Electronic Processing of Sociometric Data for Groups Up to 1000 in Size. ” American Sociological Review 25 (5): 722–727.
8.
DallasCostis.2015. “Jean-Claude Gardin on Archaeological Data, Representation and Knowledge: Implications for Digital Archaeology. ” Journal of Archaeological Method and Theory 23 (1): 305–330.
9.
De MolLiesbeth, and BullynckMaarten. 2008. “A Week-end off: The First Extensive Number-Theoretical Computation on the ENIAC.” In
Logic and Theory of Algorithms, edited by Arnold Beckmann, Costas Dimitracopoulos, and Benedikt Löwe, 158–167. Berlin and Heidelberg: Springer.
10.
De MolLiesbeth, and PrimieroGiuseppe. 2014. “Facing Computing as Technique: Towards a History and Philosophy of Computing. ” Philosophy & Technology 27 (2): 321–326.
11.
DixonAnthony Hunter.1973. “On the Efficiency of Clique Detection in Graphs.” PhD diss., The University of British Columbia.
12.
DoreianPatrick.1969. “A Note on the Detection of Cliques in Valued Graphs. ” Sociometry 32 (2): 237–242.
13.
EppsteinDavid, LöfflerMaarten, and StrashDarren. 2010. “Listing all Maximal Cliques in Sparse Graphs in Near-optimal Time.” In
International Symposium on Algorithms and Computation, 403–414. Berlin and Heidelberg: Springer.
14.
EspiratJean-Jacques, GuiartJean, LagrangeMarie-Salomé, and RenaudMonique. 1973. Système des titres, électifs ou héréditaires dans les Nouvelles-Hébrides centrales, d'Efate aux îles Shepherd. Mémoires de l'Institut d'ethnologie 10. Paris: Institut d'ethnologie.
15.
FestingerLeon.1949. “The Analysis of Sociograms Using Matrix Algebra. ” Human Relations 2 (2): 153–158.
16.
FlamentClaude.1963. Applications of Graph Theory to Group Structure. Prentice-Hall Series in Mathematical Analysis of Social Behavior. Englewood Cliffs, NJ: Prentice-Hall Inc.
17.
FlamentClaude.1965. Théorie des graphes et structures sociales. Mathématiques et sciences de l'homme 2. Paris and La Haye: Mouton and Gauthier-Villars.
18.
ForsythElaine, and KatzLeo. 1946. “A Matrix Approach to the Analysis of Sociometric Data: Preliminary Report. ” Sociometry 9 (4): 340–347.
19.
FreemanLinton C.1988. “Computers Programs and Social Network Analysis. ” Connections 11 (2): 26–31.
20.
FreemanLinton C.2004. The Development of Social Network Analysis . Vancouver, BC: Empirical Press.
21.
GardinJean-Claude.1960. “Les applications de la mécanographie dans la documentation archéologique. ” Bulletin des bibliothèques de France 5 (1–3): 5–16.
22.
GardinJean-Claude.1961. “Détermination du réseau économique des Marchands Assyriens en Cappadoce (19e siècle avant J.C.) d'après l'analyse de leurs archives (Exploitation sur ordinateur IBM 650).” In
Comptes-rendus du Séminaire sur les Modèles Mathématiques dans les Sciences Sociales. Année 1960–1961, 23–26. Paris: École pratique des hautes études: Groupe de mathématique sociale et de statistique.
23.
GardinJean-Claude.1962a. “Cartes perforées et ordinateurs au service de l'archéologie. ” La Nature 3331: 449–457.
24.
GardinJean-Claude.1962b. “De l'archéologie à l'information automatique. ” Euratom. Bulletin d'Information de la Communauté européenne de l'énergie atomique 4: 25–29.
25.
GardinJean-Claude.1965a. “A Typology of Computer Uses in Anthropology.” In
The Use of Computers in Anthropology, edited by Dell H. Hymes, Studies in Anthropology, 103–117. La Haye: Mouton & co.
26.
GardinJean-Claude.1965b. “Les travaux de la Section d'Automatique Documentaire (Institut Blaise Pascal, C.N.R.S.), 1961–1965.”
T.A. Informations, Vol. 1–2, 9–24.
27.
GardinJean-Claude.1965c. “Reconstructing an Economic Network in the Ancient East with a Computer.” In
The Use of Computers in Anthropology, edited by Dell H. Hymes, Studies in Anthropology, 377–391. La Haye: Mouton & co.
28.
GardinJean-Claude, and GarelliPaul. 1961. “Étude des établissements assyriens en Cappadoce par ordinateur. ” Annales. Histoire, Sciences Sociales 16 (5): 837–876.
29.
GardinJean-Claude, and JaulinBernard, eds. 1968. Calcul et formalisation dans les sciences de l'homme . Paris: Éditions du CNRS.
30.
HagePer, and HararyFrank. 1983. Structural Models in Anthropology. Cambridge Studies in Social Anthropology 46. Cambridge: Cambridge University Press.
31.
HaighThomas, PriestleyMark, and RopeCrispin. 2014. “Los Alamos Bets on ENIAC: Nuclear Monte Carlo Simulations, 1947–1948. ” IEEE Annals of the History of Computing 36 (3): 42–63.
32.
HalleuxRobert, and XhayetGeneviève. 2007. La liberté de chercher. Histoire du Fonds national belge de la recherche scientifique . Liège: Les éditions de l'Université de Liège.
33.
HararyFrank.1970. “Graph Theory as a Structural Model in the Social Sciences.” In
Graph Theory and its Applications, edited by Bernard Harris, Mathematics Research Center 24, 1–16. New York: Academic Press.
34.
HararyFrank, and RossIan C.. 1957. “A Procedure for Clique Detection Using the Group Matrix. ” Sociometry 20 (3): 205–215.
JaulinBernard.1961. “Sur une méthode de détermination des cliques dans un graphe symétrique.” In
Comptes-rendus du Séminaire sur les Modèles Mathématiques dans les Sciences Sociales. Année 1960–1961, 50–57. Paris: École pratique des hautes études: Groupe de mathématique sociale et de statistique.
37.
KarpRichard M.1972. “Reducibility Among Combinatorial Problems.” In
Complexity of Computer Computations, edited by Raymond E. Miller and James W. Thatcher, 85–103. New York: Plenum.
LuceR. Duncan, and PerryAlbert D.. 1949. “A Method of Matrix Analysis of Group Structure. ” Psychometrika 14 (2): 95–116.
40.
MakinoKazuhisa, and UnoTakeaki. 2004. “New Algorithms for Enumerating All Maximal Cliques.” In
Algorithm Theory – SWAT 2004, edited by Torben Hagerup and Jyrki Katajainen, 260–272. Berlin: Springer-Verlag.
41.
MoonJ. W., and MoserL.. 1965. “On Cliques in Graphs. ” Israel Journal of Mathematics 3 (1): 23–28.
42.
Mounier-KuhnPierre-Éric.2012. “Computer Science in French Universities: Early Entrants and Latecomers. ” Information & Culture 47 (4): 414–456.
43.
NewmanMark E. J., and GirvanMichelle. 2004. “Finding and Evaluating Community Structure in Networks. ” Physical Review E 69:
026113.
44.
NofreDavid.2014. “Managing the Technological Edge: The UNESCO International Computation Centre and the Limits to the Transfer of Computer Technology, 1946–1961. ” Annals of Science 71 (3): 410–431.
45.
NSF. 1959. Science Information Notes. National Science Foundation (U.S.).
46.
ÖstergårdPatric R. J.2001. “A New Algorithm for the Maximum-weight Clique Problem. ” Nordic Journal of Computating 8: 424–436.
47.
PardalosPanos M., and XueJue. 1994. “The Maximum Clique Problem. ” Journal of Global Optimization 4: 301–328.
48.
PaullMarvin C., and UngerStephen H.. 1959. “Minimizing the Number of States in Incompletely Specified Sequential Switching Functions. ” IEEE Transactions on Electronic Computers EC-8 (3): 356–367.
49.
PlutniakSébastien.2017. “Is An Archaeological Contribution to the Theory of Social Science Possible? Archaeological Data and Concepts in the Dispute Between Jean-Claude Gardin and Jean-Claude Passeron. ” Palethnologie 9: 7–21.
50.
PlutniakSébastien.2018. “Aux prémices des humanités numériques ? La première analyse automatisée d'un réseau économique ancien (Gardin & Garelli, 1961). Réalisation, conceptualisation, réception. ” ARCS 1. https://hal.archives-ouvertes.fr/hal-01870945.
51.
SchneiderMichel.1973. “Méthodes pour recenser toutes les cliques maximales et q-maximales d'un graphe. ” Revue française d'automatique, informatique, recherche opérationnelle. Recherche opérationnelle 7 (V3): 21–33.
52.
WassermanStanley, and FaustKatherin. 1994. Social Network Analysis . Cambridge: Cambridge University Press.
