1
$\begingroup$

Consider the following problem.

Let $P$ be a set where each element represents a person (i.e. $P = \{p_1, p_2, ..., p_n\})$. Let $I$ be the set of interests (i.e. $I = \{i_1, i_2, ..., i_m\}$). We are given a function $f$ s.t. $\forall p_i \in P$, $f(p_i)$ is a subset of $I$ (in other words, the function allows us to recover a given person's interests from the set of interests). Also, consider that $m << n$ (let's assume that, in our case that $m = n/10$).

Question: How many pairs of people share at least one interest?

I assume I would have to proceed the following way:

  1. Compute the number of possible pairs of people : $C{n \choose 2}$
  2. Compute the number of pairs that do not share any interest : $\sum_{i=1}^{n-1}\sum_{j=i+1}^{n} \text{is_empty}(f(p_i) \phantom{a} \cap \phantom{a} f(p_j))$ where the is_empty function simply checks if the intersection of both sets is empty and if it is the case, returns $1$ (it returns $0$ otherwise)
  3. The number of pairs that share at least one interest is $C{n \choose 2}-\sum_{i=1}^{n-1}\sum_{j=i+1 }^{n} \text{is_empty}(f(p_i) \phantom{a} \cap \phantom{a} f(p_j))$

Is there a better way for me to compute this ? (Typically, here I did not exploit the fact that $m << n$). I have large sets and I don't want to compute the double sum by hand (and I would have to enter the sets in a computer to let it run). I am looking for a lazy way out of this :p

$\endgroup$
1
$\begingroup$

In combinatorics, graphs can help solve a lot of problems.

The construction goes as such : we construct an (undirected, simple) graph $G = (V,E)$, where $V = P$ and $uv \in E$ iff $f(u) \cap f(v) = \emptyset$. The number of edges in this graph represent your your desired answer, which could be computed by summing all the elements in your adjacency matrix.

PS : The graphical method has the capacity to give you answers to queries much more than merely the number of pairs that share at least one interest. It can also give you the number of people with the largest number of common interests (i.e. the largest connected component). The number of edges of the complement of the graph will give you information on the number of people who share no interests at all. Perhaps some extra information could also be retrieved via using hyper graphs, but I need to think on that more.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.