0
$\begingroup$

I asked this question on datascience.stackexchange but they directed me here.

I have a social network represented as a set of people S and individual weights for each of person (weight is the cost of person). I also have defined relationships between these people (whether people know each other or not). I must find such a subset D, such that every person in this subset either belongs to the set S or knows someone from the set S directly.

There will be a lot of such subsets. I want the subset whose sum of weights of people is the smallest.

Let's see example:

D = {(John(7), Adam(15), Viktor(6), Bob(2)} and connections are John - Adam - Viktor - Bob. Solutions are Adam,Bob(17) OR John,Victor(13) OR Adam,Victor(21) OR John,Bob(9). The best is the last one - John,Bob(9).

I thought to create a directed graph where:

  • Each vertex represents person
  • Each vertex has a weight assigned to it
  • Edges between vertices indicate whether the people know each other or not

I imagine this as a minimum spanning tree on directed graphs problem. I found Chu-Liu/Edmond's algorithm, I know that this algorithm works for edge-weighted graphs and I have vertices-weighted, so I just set the edge weights to what are the weights of the vertices at the end of the edge. But this is not optimal solution. I don't need direct connections between people in the set D.

So after I have result from that algorithm, I can apply on it some greedy algorithm, which will go recursively over each element and check how removing it from the subset D will affect the structure - when the sum of the weights will be minimal and will ensure that no element falls out of set D (check below).

Refer to an example, my MST result will be John,Adam,Victor,Bob(27). Best solution is John,Bob(9). Interesting bad solution is Viktor,Bob(8) - the sum is minimal, unfortunately John will fall out of the D subset.

Also I assume that:

  • cost of a person doesn't correlate with their degree in the network (numbers of acquaintances)
  • the maximum number of people and acquaintances (vertices and edges) is about 400

Is my way to solve this problem is good? Do you suggest any other solutions for that?

$\endgroup$
1
$\begingroup$

First a few comments/questions about your approach:

  • Why do you think your problem has anything to do with minimum spanning trees? I fail to see the connection.
  • Why is your graph directed when the original problem seems to state that the "know eachother" relation is symmetric? (if A knows B then B knows A)
  • For your "greedy post-processing" can you do better than looking at all possible subsets of D? In other words, how does your MST help you compute the correct subset?

Then to answer your question:

If I understood you correctly, the problem you want to solve is a weighted version of dominating set. It is NP-Hard and thus unlikely to be solvable efficiently in the worst case when the number of people increases.

By googling "minimum weight dominating set" you will however find approximation algorithms, heuristics or "practically efficient" algorithms which might do the trick if the number of people in S is not too large (or the specific instance happens to be nice enough). I'm not sure how well they would perform for your considered graph size.

Alternatively, if the number of people in S is really not large (say fewer than 25) then you might consider simply brute-forcing through every possible subset of S.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ right, it's about minimum weight dominating set problem. I understand that for a large group of people it is impossible to find an exact solution in a short time. I will try one of the methods listed by you $\endgroup$ – czaduu Aug 9 at 21:08

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.