[Pgraph Logo-Canaan Genealogy] Tool Kit for the Structural Analysis of Genealogical and Marriage Data

1998 passworded Analyzing Large Kinship and Marriage Networks drw, Vladimir Batagelj and Andrej Mrvar. [published in:] Social Science Computer Review 17(3):245-274.

Advances in Scientific Knowledge

Download P-graph software for Network Analysis of Marriage & Kinship

Illustrative KineMage Animation (4 Silvia)
******click to expand the image
Illustrative Tlaxcalan Compadrazgo

Download KithKin for P-graphs

Other genealogical tools and resources

The p-graph is designed to graphically represent social networks that include, but are not limited to, kinship and marriage ties. In the general case there are two types of vertices in these graphs. One type of vertex represents organizations: families, business, or other groups to which individuals belong. The other type of vertex represents an individual and a linkage between this individual and a group. This second type of vertex exemplifies the defining feature of p-graphs: it has a maximum outdegree of two directed arcs, and the relation between vertices defined by these arcs is one of strict (temporal) order. The first type of arc is constrained by definition to these same conditions. Hence, the p-graph is asymmetric and acyclic and generates a partial ordering among the vertices.

Program Pajek for large network analysis has been implemented in various versions of the p-graph format. Genealogists and social scientists will be pleased to know that Pajek reads GEDCOM files in native format, and converts them to p-graphs using three checkbox /Options in the Pajek menu under Read / Write checkboxs:

see: topical bibliography on p-graphs

The p-graph is ideal for representing kinship and marriage networks because the two types of vertices collapse into one: each spouse descends from a family of orientation but is linked to the family of a spouse, and the new family of procreation produced by the spouses is a "group of origin" for their children. Example:

Hence in a p-graph of kinship and marriage, each vertex represents a nuclear family formed by a couple and their children (or, in the case of single individuals, a potential for forming such a family), and a maximum of two arcs point from a vertex to other vertices: the arc for a male progenitor points to his family of origin, and the arc for a female progenitor points to her family of origin. Single males or females, of course, have only a single outgoing arc to their parents or family of origin.

If the network contains other kinds of vertices that represent groups to which individuals belong, the p-graph keeps the convention that each vertex has a maximum outdegree of two: one to the family of origin of an individual, and one to another group to which the individual belongs.

The arcs in a p-graph, in any case, represent individuals with specific affiliations to families or groups. A person with multiple marriages (or belonging to multiple groups), will be represented by multiple arcs.

Note: I have a new program that makes something like Petri-Nets for Pajek Analysis: Ego2nets

P-graphs can also be represented as asymmetric and acyclic specializations of Petri-nets, or directed graphs in which there are two classes of nodes, places (groups with resources) and transitions (which, as with actors, act to transfer resources between places), and arcs are only between different classes (hence a bipartite graph). The vertices of p-graphs are all of the first type, and the individuals of our pgraphs now gain actor status as a second class of vertices. Note that the generic Petri net allows cycles. We can go from an acyclic P-Graph to a Petri net by a reduction of actors into equivalent roles over time, and link to the Petri net theory for modeling asynchronous and concurrent processes in which the only important property of time (but see timed Petri nets, below), from a logical point of view, is in defining a partial ordering of the occurrence of events. The following Petri-Net is a translation of the previous example:

History of Petri Nets [Denmark] Summary: Petri nets were originally developed in the 60'ies and the 70'ies, and they were soon recognized as being one of the most adequate and sound languages for description and analysis of synchronization, communication and resource sharing between concurrent processes.....

Petri nets also have tokens (whose current distribution is a marking, or collections of tokens marked by a sets of dots within each place) whose movements or transitions are described by the connections in the network, as by the axioms:
1. A transition, or firing of tokens, is described by the pattern of outgoing arcs (one token per arc, each being transmitted or replicated at transition points)
2. A place will fire (is enabled to fire) only when the number of tokens at that place is sufficient to be distributed to each of the outgoing arcs.

Limited as these axioms seem, they are sufficient to define a general model of computational systems, or systems in general, including systems of specifically social phenomena, such a processes of wealth accumulation, inheritance, exchange, etc.

Although the link between p-graphs and Petri nets is virtually unexplored, except for a reference to modeling biological populations in the most accessible reference book by James L. Peterson (1981:78), Petri Net Theory and The Modeling of Systems, this an area that is 'hot', especially in Europe and certain groups in the US (MIT, Worchester Tech, Maryland, Syracuse, and Digital Systems Lab, to judge from the web sites) for the computer modeling of complex systems, including computing itself. World of Petri Nets [Denmark] Summary: The Petri Net WWW pages and the Petri Net Mailing List are organized by the International Conferences on Application and Theory of Petri Nets. Published by the Special Interest Group on Petri Nets and related system models of the Gesellschaft für Informatik e.V.....

Some internet links to Petri-net are given below.

Computer Science Department Links for Petri Nets:
Shedler, G.S.
Belikov, V.K.
Normal and Sinkless Petri Nets Summary: The authors examine both the modeling power of normal and sinkless Petri nets and the computational complexities of various classical decision problems with respect to these two classes. They argue that although neither normal nor sinkless Petri nets are strictly more powerful than persistent Petri nets, the nonetheless are both capable of modeling a more interesting class of....
Suzuki, I.
Hiraishi, K.
Ghezzi, C.
Hisamura, T.
A system for the design and Analysis of Petri nets.
A Petri Net Based Environment for the Design of Event-Driven....
König, R.
Dynamic Petri Nets.
A Concept of Hierarchical Petri Nets with Building Blocks.
Vautherin, J.
Meseguer, J.
Abellard, P.
Regular marked Petri nets.
Christensen, S.
Pezzè, M.
On Petri Nets and Data Flow Graphs.
Dillon, T.S.
Interval Timed Coloured Petri Nets and their Analysis.
Petri Nets and Algebraic Specifications.
A Characterization of the Stochastic Process Underlying a St....
Berthelot, G. cui.unige.ch
Pointers to Petri Net on-line info
World of Petri Nets
History of Petri Nets
Petri Nets Standard
What's New on the Petri Nets Web
Worchester Polytech
Books and Papers on Petri Nets
Petri Net Page Summary: Object Petri Net Research; Approaches in Unifying Petri Nets and the Object-Oriented Approach....
Introduction to Timed Petri Nets
University of Maryland
Petri Nets Summary: Petri Nets is a formal and graphical appealing language which is appropriate for modelling systems with concurrency. Alan A.,Desrochers, Robert Y. Al-Jaar,"Applications of petri nets in...."
Petri Nets Simulation Documentation
Pointers to Petri Net Summary: on-line info [Geneva] Graphical Languages with a formally defined semantics/Petri Nets (a section of Formal Methods for the Specification and Design of Real-Time Safety Critical Systems). SANDS/CO-OPN, Structured Algebraic Net Development System Concurrent Object-Oriented Petri Nets....

Math Department Links for Petri Nets:
Vasilis Home Page

Other Links for Petri Nets:
Digital Systems Laboratory
Formal Methods Group at HUT/Digital Systems Laboratory
Springer's Online Pubs
Mathematical Systems Theory 30:475-494 (1997)

The above links were made in August 1998

Some new links:
Timed Petri Nets
[many "timed Petri net" references

Contact Information: US Mail: Douglas R. White School of Social Sciences 3151 Social Science Plaza University of California Irvine, CA 92697, USA Location: SSPA 4169 Office Phone: (714) 824-5893 Secretary, Lisa Mikhail: 824-5401 Home Phone: (619) 452-9957 Fax: (714) 824-4717 Internet: drwhite@uci.edu, drwhite@sdsc.edu

[] Seminars [] Projects [] Mail me

This page has been accessed times since November '97.

Links to other Social Networks web sites

Links to Networks in Society and History journal home pages and its Discussion Forum home pages

back to home page [Pgraph Logo-Canaan Genealogy]