P-graph generation levels

From InterSciWiki
Jump to: navigation, search
The deepest DAG is 1-5. This node is just above 3, that makes it generation 2 in all such cases.

Please download StructuralEndogamyandtheTheoryofGenerations1a.pdf for the Simpa Conference, and for subsequent version. -- Kinship Simulations - [Project Simpa ANR funded]] - Software: Kinship simulation pseudocode - R source to compute a DAG. -- R source codes for DAG computation and Causal Analysis.

The Question and the Algorithm, Specifically

> Hi Doug, >

The deepest DAG is 1-5. This node is just above 3, that makes it generation 2 in all such cases. Now we have anot line, but counting ups and downs there are 6 generations. Same rules apply. It the orange numbers that are correct. RULE 2: BETWEEN ANY MAXIMAL ANCESTOR AND ANY FINAL DESCENDENT ITS THE MAXIMAL DEPTH THAT GOVERNS GENERATION.

> Sorry I haven't been able to finish the generation assignment R code. As I > was writing the code, I got involved with many theoretical (and > philosophical) questions about generations and how we define them. I was > wondering if you could tell me a bit more how we define generations (I > know it's purely about the structure of the graph but even then why we > chose it to be so) > > More specifically how do we assign the generation for this person in this > graph that I am sending you a picture of? > > Regards, > > -Tolga > We choose it to be so because there cultural definitions vary. For australians is mostly: couples who link through siblings-in-law (excluding alternate generation moieties). These horizontal chains, say of br-in-law of br-in-law ... or ... br-in-law may go back hundreds of years to the invention of "section systems," where generations are defined by kinship relations. In most European or "Western" societies generation has nothing to do in many cases with kinship or marriage, a "generation" is usually defined by contemporaries. Women bear children from menarche to the early forties, so siblings and sibling-in-laws are often not contemporaries. So there is no general "philosophical" rule of generations. There is, however, a dag structure to p-graphs even though husband and wife are not necessarily of the same "European" generation, e.g., marriage with a nephew or neice, or cousin once removed etc. So the only good idea for generations mathematically is to minimize the distance between nodes in the dag. THere are no "implicit" generations in the dag. But there is always a minimal chain MC, say 5, from maximal lineal ancestor to minimal lineal descendant. In this example that MC is 5 although there is an ancestor that is at least 7 generations distant from a nondescendant. So you start from any maximal chain from a a descendant upwards, then go down (in this case 3) to the first uplink, then go up (in this case 4), etc., then you backtrack to any higher ancestor on any of these chains, and ALWAYS set their generation just 1 above. When dont with all these searches, you repeat for searches downward, and any downward link in these changes is ONE DOWN unless they have a spouse TWO OR MORE DOWN, then you have to assign a generation down MORE THAN ONE. and so forth. The } symbol means "not a child" but a link to a generationally younger spouse. This is the DOWNWARD view. The UPWARD VIEW flips the graph, does the same algorithm. This defines highest and lowest possible generations for any couple. Between these two, generation is arbitrary but DOWNWARD placement is determined and so is UPWARD.

|  /\
| |  |\
|/  |  }
|    |\| 
_____| Click "Edit" to view this graph, and ignor the ___ horizontal lines

-- Doug White http://intersci.ss.uci.edu/wiki/index.php/DW_home


Andrej Mrvar wrote successive versions of the Net/Partition/Generations algorithm for pajek, none of which correctly corresponds to genealogical generations, even the latest: If the Ac06 Ndembu dataset is analyzed and compared to the graphic corrected by hand, it will be seen that the nodes with lower ancestries do not align properly. This is illustrated for apical parents whose daughter's son's mother is placed at the level of the apical mother's parents. It is critical to empirical analysis (like the Ndembu) and to marriage randomization that generations be appropriately defined. The following algorithm, in its several variants, is crucial to the Generation permutation code or randomized marriages model, where who marries whom is randomized within generations. No assumption is made that spouses will be of the same age, on average, within generations.

Pseudocode for Minimization algorithm (Maximization of parent-child generational proximity)

Axiom. Every DAG has a maximum number of net seesaw generations, i.e., counting up and down parent-child links from a lowest descendant to highest ancestor. This can be termed the DEPTH of the DAG or MINIMAL DAG DEPTH.

  1. A DAG structure is computed for the whole graph (connected or not) and found to have k levels. The level of individual nodes need adjustment to meet the minimization criterion of forming generational levels that minimize the total of distances between parents and their children according to their adjusted levels.
  2. A simple DFS function like http://igraph.sourceforge.net/doc/R/graph.dfs.html is used for each root ancestor A to order their DAG locally by depths d(A_i).
  3. Starting from the deepest DAGS, repeat finding highest ancestors H at level h aside from the root and the DAGs of H with node levels starting with h, d(A_h).
  4. As each new DAG and its nodes under H is added, connect any edge-pair P(a,b) that have one node in each of two DAGs. (Parent and child may link with one or more separating generations).

Awaiting Proof: Condition 1 and steps 2-4 satisfy the minimization criterion. This criterion, however, can be satisfied in various ways.

  1. This solution chooses to place descendants as close to their ancestors as possible, starting from apical ancestors computed from early generations.
  2. Another solution chooses to place ancestors as close to their descendants as possible, starting from descendants at the nadir or lowest generations. To calculate, reverse the direction of arrows and run the algorithm.
  3. Third and fourth solutions are to place nodes in median positions; where ambiguous, either favoring an apical principle or a nadir principle. To calculate, run the algorithms and in reverse, double the distance between generations, and average appropriate results for the forward and reverse generations.

In principle, proof of the minimization criterion should apply to any network with a DAG (directed asymmetric graph) structure, not just a p-graph, in which parental nodes have multiple children but only two parents. Generations will, however, become increasingly fuzzier the more randomness within the DAG.

Awaiting demonstration: The minimization criterion can be satisfied even if there are significant difference in average age of marriage for men and women. (See Alyawarra)

Depth First Search


EpiContactTrace 0.6.0


  • Added the method ShortestPaths
  • NetworkStructure gives the distance from root for
 each node during the depth first search.

IGraph DFS


SimPa Conference with ooVoo participation

Paris SimPa Conference with ooVoo participation October 2012