Mutual Friends in a Network?

Question

I always seem to have trouble finding a formal way to analyze this (be through proofs or whatever).

The problem statement is as such:

If A and B are friends, and B and C are friends, then A and C are friends too.

In a simple network like the following, this makes complete sense:

1 --- 2 --- 3

Analysis: We can see that 1 and 2 are friends, and 2 and 3 are friends. It follows from the problem statement that 1 and 3 must be friends too. This is the most generic case for a problem like this.

Where I get confused is in a following network:

1 --- 2 --- 3 --- 4

Analysis: We can see that 1 and 2 are friends, and 2 and 3 are friends; therefore, 1 and 3 must be friends. Also, since 2 and 3 are friends, and 3 and 4 are friends; therefore, 2 and 4 must also be friends.

Since 1 and 2 are already friends, would it follow from our conclusion of the last sentence (that 2 and 4 are friends) that 1 and 4 must also be friends?

Moving forward into a bigger picture, any group of connected nodes would also all be friends?

What's the best way to analyze this?

Answer 1

This is a possible way you can describe it:

Define $P$ to be the set of all possible people. Then, define the relation $F\subseteq P\times P$ such that $xFy$ (or equivalently, $(x,y)\in F$) only if $x$ is a friend of $y$.

Then, the requirements you stated are translated into the relation as follows:

1. Symmetric: If $x$ is a friend of $y$ then also $y$ is a friend of $x$. Formally, this is written as $$\forall x,y:xFy\iff yFx$$
2. Transitive: If $x$ is a friend of $y$, and $y$ is a friend of $z$ then $x$ is a friend of $z$. Formally, this is written as $$\forall x,y,z:(xFy\land yFz)\implies xFz$$
3. This one actually depends on whether you consider a person to be a friend with himself. If you restrict it such that every person is "a friend with himself", then the relation is also reflexive. Formally, this means that:$$\forall x:xFx$$

The combination of the above 3 properties is known as an equivalence relation. In such an equivalence relation, it is possible to "divide" the set $P$ into disjoint subsets $C_1,\dots,C_k$ such that all people in $C_i$ are friends of all other people in $C_i$, but aren't friends of any people in $C_j$ for $j\neq i$. Those $C_i$'s, are known as equivalence classes, and are known to be unique as well.

In your two examples, the subsets would simply be the entire population, hence any two people will be friends.

On the larger scale, if $x_1$ is a friend of $x_2$ which is a friend of $x_3$ and so on until $x_n$ for some $n\in\mathbb{N}$, then all of those $x_i$'s will have to be in the same equivalence class, and hence will all be friends of each other.

Answer 2

You're probably looking for strong and weak ties, and specifically strong triadic closure.

In this framework, your graphs have two kinds of edges, strong and weak.

As you say, you shouldn't have an induced $P_3$ if the two edges are strong. In that case, the edge 1-3 should exist, either as a weak edge of a strong edge.

You are, however, allowed to have an induced $P_3$ provided that at least one of the edges are weak.

In the last case, with your $P_4$, you need the edge 1-4 of and only if all edges are strong.

Answer 3

If you don't want to apply the framework of weak and strong links, you are probably looking for the concept **transitive closure.

Yes, all pairs 1-2, 2-3, 3-4, 1-3, 2-4, as well as 1-4 will be friends in the transitive closure.