0
$\begingroup$

Relevance to Site

I believe this question is suitable for the Computational Sciences Stack Exchange site 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 paths 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.

New contributor
Jay Gupta is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.