How hard is it to classify edges as strong or weak?
A question that might naturally arise when studying strong and weak ties is: if I have a completely unlabeled graph G = (V, E), how do I label its edges as strong or weak? There is a number of ways of doing this. It can be easy to accomplish. Trivially we could randomly label each edge as strong or weak. Or, if G represents a network, we can use data from the network to decide the label of each edge. A more interesting problem is: what if I want to label the edges maintaining the Strong Triadic Closure property in such a fashion that the number of strong ties is maximum – equivalently, the number of weak ties is minimum? That’s not an easy problem to solve. Actually it is NP-hard.
In the paper Using Strong Triadic Closure to Characterize Ties in Social Networks, S. Sintos and P. Tsaparas prove that labeling such graph is NP-hard by reducing the problem to a ego-network variant. And then they prove that although the algorithm to solve such problem is NP-hard, there are O(log n) approximations to the solution. The basic approach of the solution, in a shell, would be to consider chiefly the edges that participate in an open triangle, to set one of the edges in this triangle as weak, and to maintain the number of weak ties as small as possible, thus minimizing it.
The idea of characterizing ties in a social network in an optimal way such that the Strong Triadic Closure property is satisfied is novel and open to research. Particularly, if we consider edges not only as only weak and strong, but with degrees of how strong the ties actually are, that would create an even more interesting research topic. One that could be the topic of research to any of us.
Source: S. Sintos, P. Tsaparas, Using Strong Triadic Closure to Characterize Ties in Social Networks. ACM International Conference on Knowledge Discovery and Data Mining (KDD), August 2014.