Rule-Based Link Prediction for Social Network

Question

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.

Answer 1

Once you know the "parent" and "spouse" relationships, everything else can be derived. So one approach would be to decompose the problem into two steps:

1. Infer all parent and spouse relationships that can be derived from the given graph.

2. Infer all other relationships, from the derived parent and spouse relationships.

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.