Finding Matrimonial Circuits in some AmerindianKinship Networks
We consider the problem of deciding the existenceof matrimonial circuits, and finding implexa in kinship networks.These networks can be modeled by acyclic digraphs. A mat-rimonial circuit can be seen as vertex-disjoint directed pathsfrom special starting to special ending vertices of these acyclicdigraphs. An implex is the set of all matrimonial circuits ofa given pair of special vertices. We present methods based onEppstein’s reduction [3] and algorithms for finding junctions [5]to decide the existence of matrimonial circuits. The efficiencyof these methods is shown in our empirical results on sevenAmerindian kinship networks. To enumerate all implexa, wepresent an algorithm, given that the kinship network is limited.We present some descriptive statistics which help us to justifythe good performance of the methods. We incorporate to oursoftware tool, the Kinship Machine [2], a feature to enumeratematrimonial circuits. This tool is being used by Anthropologiststo analyze Amerindian kinship networks of northern Brazil.
The origins of the present work are in both areas of Human-ities and Graph Theory. More specifically, in the difficulty ofanalyzing without the help of computer tools kinship networks.On the other hand, the search of these structures in thosegraphs gives rise to interesting problems in Computer Science.L ́evi-Strauss [10] developed thealliance theory, demon-strating that the origin and the regulation function of kinshipis to be found in exchange in all its forms. The idea ofmarriage alliancesemerges from the interdependence of socialentities like individuals, families, clans, lineages, etc., in agiven society. In this seminal book, the author classified someforms of matrimonial circuit, found in empirical genealogicalnetworks, in terms of their implications for social cohesion.In other words, he demonstrated how patterns of marriageintegrate social groups.Marriages not only create ties of consanguinity and affinity,but also are determined by them. What are the basic formsof relatedness by which ties of social integration are con-structed through marriage? According to Richard [12], White[14], Hamberger, Houseman, Daillant, White and Barry [8],matrimonial circuits, or “ring” structures, are particular typesof cycles in kinship networks which result when spouses arelinked to each other by ties of consanguinity or affinity. Thestudy of matrimonial circuits is the starting point of any anal-ysis of how kinship relatedness (consanguinity and affinity)actually determine matrimonial choices. Moreover, the studyof these structures in empiricalkinship networks provides anew approach to the comparative study of marriage systems.Hence, this is the anthropological interest in computationalmodeling of kinship in small scale societies. Next we formallydefine all the concepts used in this work. They are consistentwith those described in [9] and [2].Theempirical kinship networkis understood as a finite setof vertices (individuals) andlines, or edges and arcs (kinshipconnections). A connection corresponds to an immediate filia-tion (F, M, S or D) or marriage (W or H) relation, in terms of itssocial recognition, so that each connection may be expressedby the ordered pair of individuals (ego, alter) and the type ofkinship tie they have. Therefore, in terms of Graph Theory,akinship networkis amixed graphformed by a finite set ofindividuals represented by vertices, a finite set of marriagesrepresented by edges (undirected lines), and each parent-childrelationship defines an arc.Anoriented cycleis a digraph where each vertex has in-degree and out-degree equal to 1. In a mixed graph we defineacycleas a subgraph whose vertices have degree 2 (arcsand edges counted) and directions do not matter. There is nooriented cycle in a kinship network (an individual could notbe his own ancestral) but there may be cycles.