Metodoloˇski zvezki, Vol. 1, No. 2, 2004, 407-418
Relinking Marriages in Genealogies
Andrej Mrvar1 and Vladimir Batagelj2
Abstract
Genealogies can be represented as graphs in different ways: as Ore graphs, as p-graphs, or as bipartite p-graphs. p-graphs are usually more suitable for analyses. Some approaches to analysis of large genealogies implemented in program Pajek are presented and illustrated with analysis of some large ge-nealogies.
1    Sources of genealogies
People collect genealogical data for several different reasons/purposes:
•  Research on different cultures in history, sociology and anthropology (White et al., 1999), where kinship is taken as a fundamental social relation.
•  Genealogies of families and/or territorial units, e.g.,
– Mormons genealogy (MyFamily.com, 2004)
ˇ – genealogy of Skofja Loka district (Hawlina, 2004)
– genealogy of American presidents (Tompsett, 1993)
•  Special genealogies
– Students and their PHD thesis advisors:
Theoretical Computer Science Genealogy (Johnson and Parberry, 1993)
– gods (antique). See Hawlina (2004).
There also exist many programs for genealogical data entry and maintenance (GIM, Brother’s Keeper, Family Tree Maker,...), but only few analyses can be done using the programs. We use Pajek for analyses and visualization of ge-nealogies.
Faculty of Social Sciences, University of Ljubljana, Slovenia; andrej.mrvar@uni-lj.si Faculty of Mathematics and Physics, Univ. of Ljubljana, Slovenia; vladimir.batagelj@uni-lj.si
408
Andrej Mrvar and Vladimir Batagelj
2
GEDCOM standard
GEDCOM is a standard for storing genealogical data, which is used to interchange and combine data from different programs, which were used for entering the data. The following lines are extracted from the GEDCOM file of European Royal families.
0 HEAD	0 @I115@ INDI
1 FILE ROYALS.GED	1 NAME William Arthur Philip/Windsor/
	1 TITL Prince
0 @I58@ INDI	1 SEX M
1 NAME Charles Philip Arthur/Windsor/	1 BIRT
1 TITL Prince	2 DATE 21 JUN 1982
1 SEX M	2 PLAC St.Mary’s Hospital, Paddington
1 BIRT	1 CHR
2 DATE 14 NOV 1948	2 DATE 4 AUG 1982
2 PLAC Buckingham Palace, London	2 PLAC Music Room, Buckingham Palace
1 CHR	1 FAMC @F16@
2 DATE 15 DEC 1948	...
2 PLAC Buckingham Palace, Music Room	0 @I116@ INDI
1 FAMS @F16@	1 NAME Henry Charles Albert/Windsor/
1 FAMC @F14@	1 TITL Prince
...	1 SEX M
...	1 BIRT
0 @I65@ INDI	2 DATE 15 SEP 1984
1 NAME Diana Frances /Spencer/	2 PLAC St.Mary’s Hosp., Paddington
1 TITL Lady	1 FAMC @F16@
1 SEX F	
1 BIRT	0 @F16@ FAM
2 DATE 1 JUL 1961	1 HUSB @I58@
2 PLAC Park House, Sandringham	1 WIFE @I65@
1 CHR	1 CHIL @I115@
2 PLAC Sandringham, Church	1 CHIL @I116@
1 FAMS @F16@	1 DIV N
1 FAMC @F78@	1 MARR
...	2 DATE 29 JUL 1981
	2 PLAC St.Paul’s Cathedral, London
From data represented in the described way we can generate several graphs as explained in next chapters.
3
Representation of genealogies using networks
Genealogies can be represented as networks in different ways: as Ore-graph, as p-graph, and as bipartite p-graph.
3.1
Ore-graph
In an Ore graph of genealogy every person is represented by a vertex, marriages are represented with edges and relation is a parent of is represented as arcs pointing from each of the parents to their children. See Figure 1.
Relinking Marriages in Genealogies
409
Figure 1: Ore graph.
grandfather-f & grandmother-f
grandfather-m & grandmother-m
Figure 2: p-graph.
3.2
p-graph
In a p-graph vertices represent individuals or couples. In case that person is not married yet (s)he is represented by a vertex, otherwise the person is represented with the partner in a common vertex. There are only arcs in p-graphs – they point from children to their parents (Figure 2). The solid arcs represent the relation is a son of and the dotted arcs represent relation is a daughter of.
410
Andrej Mrvar and Vladimir Batagelj
(^__jsister-in-law
sister
.son-in-law
father & stepmother \    ^stepmother
V,___/grandmother-f
Figure 3: Bipartite p-graph.
grandmother-m
3.3
Bipartite p-graph
A bipartite p-graph has two kinds of vertices – vertices representing couples (rectan-gles) and vertices representing individuals (circles for women and triangles for men) – therefore each married person is involved in two kinds of vertices (or even more if he/she is involved in multiple marriages). Arcs again point from children to their parents (see Figure 3).
3.4    Comparison of different presentations
p-graphs and bipartite p-graphs have many advantages (see White et al., 1999):
•  there are less vertices and lines in p-graphs than in corresponding Ore graphs;
•  p-graphs are directed, acyclic networks;
•  every semi-cycle of the p-graph corresponds to a relinking marriage. There exist two types of relinking marriages:
– blood marriage: e.g., marriage among brother and sister.
– non-blood marriage: e.g., two brothers marry two sisters from another family.
•  p-graphs are more suitable for analyses.
Relinking Marriages in Genealogies
411
Bipartite p-graphs have an additional advantage: we can distinguish between a married uncle and a remarriage of a father (see Figures 2 and 3). This property enables us, for example, to find marriages between half-brothers and half-sisters.
4    Genealogies are sparse networks
We will call genealogy regular if every person in it has at most two parents. Genealogies are sparse networks - number of lines is of the same order as the number of vertices. In this section some approximations and bounds on the number of lines in different kinds of regular genealogies are given.
For the directed part of an regular Ore genealogy the approximation of the number of arcs A is:
|A| =     ^ din(v) ?2|V| veV
where V is set of vertices, and din(v) input degree of vertex v, din(v) ? 2. Most of the persons are married only once, some are not married. For the undirected part of an Ore genealogy the number of edges (E) is
|E| ? -|V|
Therefore
|L| = |A| + |E| ? 5 |V|
p-graphs are almost trees - deviations from trees are caused by relinking marriages. Let us denote the number of vertices of p-graph with |Vp| and the number of multiple marriages with nmult. Then, since |E| equals to the number of couples,
|Vp| = |V| - |E| + nmult
and therefore
|V| ? |Vp| ? |V|-|E| ? -|V|
The number of arcs in p-graph is
|Ap| = ]T dout(v) ? 2|Vp| veVp
where dout(v) is output degree of vertex v.
For the number of vertices Vb in a bipartite p-graph, we have
|Vb| = |V| + |E| Since |E| ? ±|V| we get
|V| ? |Vb| ?
412
Andrej Mrvar and Vladimir Batagelj
Table 1: Number of vertices and number of lines in Ore graphs and p-graphs
for some large networks.
data	\V\	\E\	\A\	\V\	Vi	nmult	1Vp1	\Ap\	\Ap\ \Vp\
Drame Hawlina Marcus Mazol President Royale	29606 7405 702 2532 2145 17774	8256 2406 215 856 978 7382	41814 9908 919 3347 2223 25822	1.69 1.66 1.62 1.66 1.49 1.87	13937 2808 292 894 282 4441	843 215 20 74 93 1431	22193 5214 507 1750 1260 11823	21862 5306 496 1794 1222 15063	0.99 1.02 0.98 1.03 0.97 1.27
Loka Silba Ragusa Tur Royal92	47956 6427 5999 1269 3010	14154 2217 2002 407 1138	68052 9627 9315 1987 3724	1.71 1.84 1.89 1.89 1.62	21074 2263 2347 549 1003	1426 270 379 94 269	35228 4480 4376 956 2141	36192 5281 5336 1114 2259	1.03 1.18 1.22 1.17 1.06
For the number of arcs Ab we have
\Ab\ = \Ap\ - nmult + 2\E\ < 2(\Vp\ + \E\) - nmult = 2\V\ + nmult
To check the results we take several large genealogies and look at the corresponding Ore and p-graphs. A comparison of Ore and p-graph is given in Table 1. In the table the following notation is used:
•   Ore genealogy: \V\ - number of vertices; \E\ - number of edges; \A\ - number of arcs; \L\ = \E\ + \A\ - total number of lines.
•  p-graph:  \Vi\ - number of individuals; nmult - number of multiple marriages; 1Vp1 = 1Vi1 + 1E1- total number of vertices; \Ap\ - number of arcs.
p-graphs are usually used also for visual representation of genealogies. Since they are acyclic graphs the vertices can be assigned to levels (see Figure 4 and Figure 5).
5    Relinking index
The relinking index is a measure of relinking by marriages among persons belonging to the same families. A special case of relinking is a blood-marriage in which the man and woman from the couple have a common ancestor.
Let n denotes number of vertices in p-graph, m number of arcs, k number of weakly connected components, and M number of maximal vertices (vertices having output degree 0, M > 1). If a p-graph is a forest (consists of trees), then m = n-k, or k + m-n = 0.
In a regular genealogy, m < 2(n - M) = 2n - 2M. Thus:
0<k+m-n<k+n-2M
Relinking Marriages in Genealogies
413
o      o      o
Figure 4: Patterns with relinking index 1 (p-graph).
or
0? k + m-n ?1
k +n-2M This is called the relinking index (RI):
RI =
k +m-n
k +n-2M
If we take a connected genealogy (selected weakly connected component) we get
m-n+1
RI =
n-2M +1
For a trivial graph (having only one vertex) we define RI = 0.  See also White et al, 1999.
RI has some interesting properties:
•   0 ? RI ? 1
•   If a network is a forest/tree, then RI = 0 (no relinking).
•   For a cycle h = f = f, RI = ^ih (the higher depth the weaker relinking). For a cycle of depth 3 (6 vertices) RI = |.
•  There exist genealogies having RI = 1 (the highest relinking). Figure 4 shows such situations.
-  marriage between brother and sister (n= 2,m= 2,k = 1, M = 1),
-  two brothers married to two sisters from another family (n = 4, m = 4,k=1,M = 2),
-  more complicated situations (n = 9, m = 12, k = 1, M = 3).
Arbitrary large genealogies with R = 1 exist.
Usually we compute the relinking index over the biconnected subgraph (or its largest component) of a given genealogy.
414
Andrej Mrvar and Vladimir Batagelj
A2
O
A4.1
A5.1
A6.1
B6.1
A3
B4
A4.2   a
A5.2
B5
A6.2
A6.3
C6
B6.4
B6.2ja        •.   B6.3   Ji
Figure 5: Relinking marriages (p-graphs with 2 to 6 vertices).
6
Relinking patterns in p-graphs
In Figure 5 all possible relinking marriages in p-graphs containing from 2 up to 6 vertices are presented (subtypes and variants as to sex are not included). Patterns are labeled in the following way:
•  first character: A – pattern with a single first vertex (vertex without incoming arcs), B – pattern with two, and C – pattern with three first vertices.
•  second character: number of vertices in pattern (2, 3, 4, 5, or 6).
•  last character: identifier (if the two first characters are identical).
It is easy to see that patterns denoted by A are exactly the blood marriages. Also, in every pattern the number of first vertices equals to the number of last vertices.
Relinking Marriages in Genealogies
415
Table 2: Comparison of genealogies according to distribution of patterns.
pattern	Loka	Silba	Ragusa	Tur	Royal	E
A2 A3 A4.1 B4 A4.2 A5.1 A5.2 B5 A6.1 A6.2 A6.3 C6 B6.1 B6.2 B6.3 B6.4	1 1 12 54 0 9 0 19 28 0 0 10 0 27 47 0	0 0 5 25 0 7 0 11 28 2 0 12 1 39 30 0	0 0 3 21 0 4 0 47 2 0 0 19 2 63 82 5	0 0 65 40 0 15 0 19 69 0 0 15 0 53 46 3	0 3 21 7 0 13 0 8 13 1 0 5 0 12 13 0	1 4 106 147 0 48 0 104 140 3 0 61 3 194 218 8
blood-marriages relinking-marriages	51 157	42 118	9 239	149 176	51 45	302 735
no. of individuals vertices in p-graph no. of couples	47956 35228 14154	6427 4480 2217	5999 4376 2002	1269 956 407	3010 2141 1138	
no. of bicon. comp. largest bicon. comp. RI (largest bicon. comp.)	29 4095 0.55	4 1340 0.78	2 1446 0.74	3 250 0.75	5 435 0.37	
6.1    Comparing genealogies
Using frequency distributions for different patterns we can compare different ge-nealogies As examples we take five genealogies:
ˇ
•  Loka.ged – genealogy in Skofja Loka district (western part of Slovenia). Data
collected by P. Hawlina.
•  Silba.ged – genealogy of island Silba, Croatia. Data collected by P. Hawlina. Here we expect high relinking because of special geographical position (isolation).
•  Ragusa.ged – genealogy of Ragusan noble families between 12 and 16 century (Mahnken, 1960; Dremelj et al., 2002). High relinking is expected because of very restricted marriage rules: member of a noble family is supposed to marry another member of a noble family.
•  Tur.ged – genealogy of Turkish nomads (White et al., 1999). A relinking marriage is a signal of commitment to stay within the nomad group.
•  Royal.ged – genealogy of European royal families.
416
Andrej Mrvar and Vladimir Batagelj
Frequency distributions are given in Table 2. We can make the following obser-vations:
•  Probability of generation jump for more than one generation is very low (pat-terns A4.2, A5.2 and A6.3 do not appear in any genealogy, pattern A6.2 ap-pears twice in Silba genealogy and once in Royal, pattern B6.4 appears five times in Ragusa and thee times in Tur).
•  In Tur there are a lot of marriages of types A4.1 and A6.1 (marriages among grandchildren and grand grandchildren).
•  For all genealogies number of relinking ’non-blood’ marriages (e.g. patterns B4, B5, C6, B6.1, B6.2, B6.3 and B6.4) is much higher than number of blood marriages. That is especially true for Ragusa where for ’critical’ marriages a special permission of pope was needed.
There were also economic reasons for non-blood relinking marriages: to keep the wealth and power within selected families.
The number of individuals in genealogy Tur is much lower than in others, Silba and Ragusa are approximately of the same size, while Loka is much larger genealogy, what we must also take into account.
We take this into account in Table 3 with normalized frequencies for number of couples in the p-graph x 1000. It can be easily noticed that most of the relinking marriages happened in the genealogy of Turkish nomads; the second is Ragusa while relinking marriages in other genealogies are much less frequent.
Table 3: Frequencies normalized with number of couples in p-graph × 1000.
pattern	Loka	Silba	Ragusa	Tur	Royal
A2	0.07	0.00	0.00	0.00	0.00
A3	0.07	0.00	0.00	0.00	2.64
A4.1	0.85	2.26	1.50	159.71	18.45
B4	3.82	11.28	10.49	98.28	6.15
A4.2	0.00	0.00	0.00	0.00	0.00
A5.1	0.64	3.16	2.00	36.86	11.42
A5.2	0.00	0.00	0.00	0.00	0.00
B5	1.34	4.96	23.48	46.68	7.03
A6.1	1.98	12.63	1.00	169.53	11.42
A6.2	0.00	0.90	0.00	0.00	0.88
A6.3	0.00	0.00	0.00	0.00	0.00
C6	0.71	5.41	9.49	36.86	4.39
B6.1	0.00	0.45	1.00	0.00	0.00
B6.2	1.91	17.59	31.47	130.22	10.54
B6.3	3.32	13.53	40.96	113.02	11.42
B6.4	0.00	0.00	2.50	7.37	0.00
Sum	14.70	72.17	123.88	798.53	84.36
Relinking Marriages in Genealogies
417
Using p-graphs, we cannot distinguish persons married several times. In this case we must use bipartite p-graphs. Using bipartite p-graphs we can find marriages between half-brothers and half-sisters (as pattern shown on the left side of Figure 6). In the five genealogies we found only one such example in Royal.ged (right side of Figure 6).
Figure 6: Bipartite p-graphs: Marriage between half-brother and half-sister (left) and
example of such marriage (right).
There exist marriages between half-cousins (Figure 7, left). We found one such marriage in the Loka genealogy (right side of Figure 7) and four in the Turkish genealogy.
1 Benjamin Simoniti & Natalija Mavric
ABenjamin Simoniti
X^Natalija Mavric
QAnton Simoniti & Jozefa Mavric    QAlojz Mavric & Angela Zuljan
ÖJozefa Mavric
Josip Mavric & Marjuta Zamar
Aalojz Mavric
Josip Mavric & Rezka Zamar
ÄJosip Mavric
Figure 7: Bipartite p-graphs: Marriage among half-cousins (left), and example of such
marriage (right).
418
Andrej Mrvar and Vladimir Batagelj
References
[1] Batagelj, V. (1996): Ragusan families marriage networks. Developments in Data Analysis, Metodoloˇski zvezki, 12, Ljubljana: FDV, 217-228.
[2] Dremelj, P., Mrvar, A., and Batagelj, V. (1999): Rodovnik dubrovniˇskih plemiˇskih druˇzin med 12. in 16. stoletjem. Drevesa. Bilten slovenskega ro-doslovnega druˇstva. 1-4, 4-11.
[3] Dremelj, P., Mrvar, A., and Batagelj, V. (2002): Analiza rodoslova dubrovaˇckog vlasteoskog kruga pomoˇcu programa Pajek. Anali Zavoda povij. znan. Hrvat. akad. znan. umjet. Dubr. 40, 105-126.
[4] Family History Department (1996): Standard GEDCOM. http://homepages.rootsweb.com/~pmcbride/gedcom/55gctoc.htm
[5] Hawlina, P. (2004): Slovenian Genealogical Society. http://genealogy.ijp.si/slovrd/rd.htm
[6] Johnson, D.S. and Parberry, I. (1993): Theoretical Computer Science Geneal-ogy. http://sigact.acm.org/genealogy/
[7] Krivoˇsiˇc, S. (1990): Stanovniˇstvo Dubrovnika i Demografske Promjene u Proˇslosti. Dubrovnik: Zavod za povijesne znanosti JAZU u Dubrovniku.
[8] Mahnken, I. (1960): Dubrovaˇcki Patricijat u XIV Veku. Beograd: Nauˇcno delo.
[9] Mrvar, A. and Batagelj, V. (1997): Pajek – program za analizo obseˇznih omreˇzij. Uporaba v rodoslovju. Drevesa. Bilten slovenskega rodoslovnega druˇstva. 12, december 1997, 4-6.
[10] MyFamily.com (2004): Mormons genealogy. http://www.familytreemaker.com/00000116.html
[11] de Nooy, W., Mrvar, A., and Batagelj, V. (2004): Exploratory Social Network Analysis with Pajek. New York: Cambridge University Press. (Forthcoming)
[12] Ore, O. (1963): Graphs and Their Uses. New York: Random House.
[13] Tompsett, B. (2004): American presidents GEDCOM file. http://www3.dcs.hull.ac.uk/public/genealogy/presidents/gedx.html
[14] White, D.R., Batagelj, V., and Mrvar, A. (1999): Analyzing Large Kinship and Marriage Networks with Pgraph and Pajek. Social Science Computer Review – SSCORE, 17, 245-274.
[15] White, D.R. and Jorion, P. (1992): Representing and Computing Kinship: A New Approach. Current Anthropology, 33, 454-462.
[16] White, D.R. and Jorion, P. (1996): Kinship Networks and Discrete Structure Theory: Applications and Implications. Social Networks, 18, 267-314.