# Efficient Generation of Subgraphs (or, unfriend a friend a day)

NB: If you're not interested in the back-story, you could simply jump forward to the code which I'm seeking to optimize. Also, I believe this code would only work for MMA 8.0 and above.

My friends and I were discussing the issue of social networks when one of us mentioned what the effect of each person removing a friend a day would be. As we made some calculations (on some rather artificial situations), we realized that it would be interesting to find out the average number of days that would be required before everyone would be left with no friends. The rules that were decided upon were as follows.

1. A set of $n$ people are considered, each pair of whom are either friends or not.
2. Before the start of each day, anyone who no longer has any friends are removed.
3. During each day, each of the remaining people picks one of his friends to unfriend.
4. Consider two people who are initially friends - Alice and Bob. If Alice decides to unfriend Bob or vice versa, then their friendship will be eliminated; if both happen to decide to unfriend each other on the same day, the same occurs.
5. No additional friendships are made on any of the days.

While the maximum and minimum number of days before everyone would be left with no friends is quite easy to analyze, the average number of days wasn't so easy to analyze mathematically. Seeing as I had Mathematica, I decided to try the following code...

isolatedVertexRemover = Function[{inputGraph},
degreeList = VertexDegree[inputGraph];
IndexGraph@VertexDelete[inputGraph, _?(degreeList[[#]] == 0 &)]];

Clear[func];
func[SystemGraph[List[], List[]]] = 0;
func[testGraph_] := func[testGraph] =
(testAdjacencyList =
AdjacencyList[testGraph, #] & /@ VertexList[testGraph];
daughterGraphs =
EdgeDelete[testGraph,
MapThread[UndirectedEdge,
Transpose@

Union[Sort /@ Transpose@{VertexList[testGraph], #}]]] & /@
Tuples[testAdjacencyList];
daughterTally =
Transpose@{isolatedVertexRemover /@
IndexGraph /@ #[[1]], #[[2]]/
Total@#[[2]]} &@
Transpose@Tally[daughterGraphs, IsomorphicGraphQ];
(1 + Total[(Map[func, #[[1]]]*#[[2]])]) &@
Transpose@daughterTally);


Then, to find out the average number of days before all people are left with no friends, one can simply run the code as follows (the example graph given is for a set of 5 people all of whom are initially friends with each other).

func[CompleteGraph[5]]


The problem with this function is that, even thought it is defined recursively, it nevertheless still takes a very long time to run. For a complete graph of size 6, the function takes only 17 seconds to run on my system, but I have not been able to obtain a result for a complete graph of size 7 and above. In fact, most graphs larger than size 10 simply cause the system to abort during the first step of the generation of the daughter graphs.

My question, therefore, is: How can we optimize the above code? The area to focus on, in my opinion, would be in the generation of the daughterGraphs`. Currently, I am simply considering all possible ways in which people can unfriend each other without taking into account the possible symmetries in the graph (for example, a case where two people are friends with exactly the same set of friends). This is a rather brute-force method which I'm sure can be improved.

Thank you for reading until here - hope you enjoyed the question, and any mathematical insight into this specific issue or perhaps the problem in general would be appreciated.

• With 10 people, they each have a choice of 9 unfriendings, giving $9^{10}$ possibilities. The next day there is probably still 10 people with 8 choices, so the total possibilities so far is $9^{10} 8^{10}$. This gets very big, very fast. I don't think you are going to brute force it. Jun 20 '13 at 21:31
• @wxffles - the probabilities are not exactly as you outline them but you are in the correct order of magnitude. (for instance, in the extreme case of one person getting unfriended by everybody, there will be 9 people left with 8 choices each). exactly why I'm hoping for a more efficient algorithm that takes into account isomorphisms in some way. Jun 21 '13 at 1:38