# Relevance to Site

I believe this question is suitable for the Computer Science Stack Exchange as it pertains to the implementation of a graph algorithm. According to this widely accepted answer, such questions are appropriate for this community. This is not a Homework Question and strictly out of personal interest.

# Summarize The Problem

Assume we are working in the Eskimo Kinship System and only allow the following family relationships.

• Parent (Mother, Father)
• Child (Son, Daughter)
• Sibling (Brother, Sister)
• Grandparent (Grandmother, Grandfather)
• Grandchild (Grandson, Granddaughter)
• Aunt, Uncle
• Niece, Nephew
• Cousin
• Spouse (Husband, Wife)
• In-law (Mother-in-law, Father-in-law, Sister-in-law, Brother-in-law, Daughter-in-law, Son-in-law)
• Stepparent (Stepmother, Stepfather)
• Stepchild (Stepson, Stepdaughter)
• Half-sibling (Half-brother, Half-sister)

The problem is to devise an algorithm for filling in all missing relationships in a social network composed of these relationships. For concreteness, consider the following situation:

V = {Man, Woman, Boy, Girl}
E = {{Man, Woman, Wife}, {Man, Boy, Son}, {Boy, Girl, Sister}}
G = (V, E)


I would like a function fillMissingRelationships(G) that adds the following edges:

{{Man, Girl, Daughter}, {Woman, Man, Husband}, {Woman, Boy, Son}, {Woman, Girl, Daughter}, {Girl, Man, Father}, {Girl, Woman, Mother}, {Girl, Boy, Brother}, {Boy, Man, Father}, {Boy, Woman, Mother}}


# Provide details and any research

On Stack Exchange I have found no mention of this specific problem. The literature primarily concerns itself with non-rule based methods for link prediction that cannot be trivially adapted to this context. If this is a duplicate or a problem with a well-known solution, please let me know in the comments and I will delete this question.

# When appropriate, describe what you’ve tried

I have reasoned about the properties of this graph. I introduce one definition and two conjectures that I believe are useful to this problem:

1. Define primary relationships as the smallest set of relationships such that every other relationship may be expressed as an ordered sequence of them.
2. We should only concern ourselves with primary relationships because other relationships are ambiguous. For instance, knowing two people are cousins does not offer much information.
3. Relationships are at most 3-rd order. This is to say, if a named relationship between two people exists in this graph, it is at most 3 hops away via primary relationships.

My instinct is to start by omitting all non-primary relationships. Then, we use an All Pairs Shortest Path algorithm (e.g., Floyd–Warshall) to find the shortest path between all people in the graph. From there, we use a lookup table mapping an ordered pair or triplet of primary relationships to one of the named relationships listed above.

I have a couple concerns. For one, it is unclear what the primary relationships are. For another, even if the proposed algorithm would work in principle (i.e., captures all possible relationships that could be inferred), its Time and Space complexity might make it prohibitive for large graphs. Finally, in the ideal case, the solution would not be difficult to implement.

• I think you are looking for something like a transitive closure. For example, {Man, Boy, Son} and {Boy, Girl, Sister} together would imply {Man, Girl, Daughter}. There are nice solutions available for that. Commented Jul 15 at 12:53
• @codeR, sorry to bother you, but could you point me to a sample solution? I looked at transitive closure and while it seems related I do not think it directly answers this question. This text defines it as "the set of pairs of nodes (u,v) such that there is a path from u to v of length zero or more." Here, I am more interested in finding the set of all missing edges. Commented Jul 15 at 17:24
• @D.W. has given a detailed answer. Maybe you should first try to explore and implement it on your own if it is for educational purposes. It would be a good exercise to understand how logical inferences work. Commented Jul 16 at 4:52

Step 2 seems easy. You just need to write down a bunch of logic inference rules, e.g., $$\text{Parent}(A,B) \land \text{Parent}(B,C) \implies \text{Grandparent}(A,C)$$, etc., with parent/spouse relationships on the left of the $$\implies$$ and other relationships on the right. It is easy to fill them in by pattern-matching.
Step 1 might be more challenging. I'm not sure. I think one possible approach would be to introduce a boolean variable $$x_{A,B}$$ for each pair of people $$A,B$$, which is intended to represent $$\text{Parent}(A,B)$$, and a boolean variable $$y_{A,B}$$, intended to represent $$\text{Spouse}(A,B)$$, and then use the logic inference rules above to write down all known facts about the boolean variables that can be obtained from the original graph. For instance, if we have an edge in the graph indicating $$\text{Grandparent}(A,C)$$, then we can write down the fact $$\bigvee_B (x_{A,B} \land x_{B,C})$$. In this way, we obtain a system of constraints on the boolean variables $$x,y$$. Then, you could use a constraint solver or SAT solver to find what this implies about the values of the $$x,y$$ variables.