# 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 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?

• – D.W.
Aug 9 '20 at 18:28

• 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?