# social network analysis - relations between people with weights

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 $$D$$ or knows someone from the set $$D$$ 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?

• – D.W. Aug 9 at 18:29

This is the minimum weight dominating set problem. You can solve it via integer linear programming as follows. For node $$i \in S$$, let $$w_i$$ be the weight and let $$N_i \subseteq S$$ be the set of neighbors. Let binary decision variable $$x_i$$ indicate whether $$i \in D$$. The problem is to minimize $$\sum_{i \in S} w_i x_i$$ subject to $$x_i + \sum_{j \in N_i} x_j \ge 1 \quad \text{for i \in S}$$