Improving your Facebook feed / Maximizing closeness and betweenness centrality

News  ·  

One sentence summary: Increasing your importance in Facebook by making new friends is quite hard in theory.

Say you could befriend any k persons on Facebook. Who would you add so that you get the most out of your feed? That seems hard to measure but let’s suppose that your feed gets more useful the more central you are in Facebook. What does it mean to be central? There are many measures for that. In this paper we looked at the betweenness centrality and closeness centrality of you in the friendship graph. Intuitively, the closeness centrality measures how many other people you can reach by making just a few hops from one friend to another. The betweenness centrality measures how many pairs of people there are such that, if we go from one to the other with the fewest number of friendship-hops, then we will see your profile. So, we could formalize maximizing your feed’s usefulness as maximizing your betweenness or closeness centrality in the friendship network by adding k new friends.

What we showed in this paper [1] is that in theory it is quite hard to maximize the betweenness or closeness centrality, also for networks which share some properties with the friendship graph of Facebook. This is a little at odds with some recent papers [2, 3] that show that there are simple greedy strategies that work quite well in practice. We also showed that there might be some efficient algorithms if the network consists of some set of disconnected communities. I think that this hints at some structure that the hardness results do not capture and I’m excited to revisit this question at some point.

This is a paper based on Clemens Hoffmann’s master thesis which I co-supervised at TU Berlin.

  1. The Parameterized Complexity of Centrality Improvement in Networks, Hoffmann, C., Molter, H., Sorge, M. In: Proceedings of the 44th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM ’18). pp. 111–124. Springer (2018).
  2. Greedily Improving Our Own Closeness Centrality in a Network, Crescenzi, P., D’Angelo, G., Severini, L., Velaj, Y. ACM Transactions on Knowledge Discovery from Data. 11, 9:1–9:32 (2016).
  3. On the Maximum Betweenness Improvement Problem, D’Angelo, G., Severini, L., Velaj, Y. Electronic Notes in Theoretical Computer Science. 322, 153–168 (2016).