Unraveling Social Ties: A New Perspective on Edge Strength Inference
Discussed throughout the early portion of this class, Strong triadic closer is a concept which determines the nature of the interconnectivity presented to us via a network graph. I would like to end my time in this class by discussing the paper “Relaxing the strong triadic closure problem for edge strength inference’. This paper showcases the intersection between emerging graph theory and the previously established concepts from the class. Many networks are binary in vie; either individuals are connected via a tie, or they are not connected at all. While paths may exist bridging the world together, disparate portions cannot research each other.
This blog post delves into a paper published on January 17, 2020, that proposes a novel approach to understanding what total graph connectivity may be like even with disparate parts.
The background:
The paper builds on the Strong Triadic Closure (STC) property, a concept rooted in sociology. STC posits that if person A has strong ties with both B and C, then B and C must also be connected, forming a triad. Previous work by Sintos and Tsaparas (2014) introduced the STC property for edge strength inference, formulating it as an NP-hard maximization problem. This basically meant that the number of strong edges would be maximized within the graph to ensure interconnectivity, increasing the prevalence of strong connections and relationships throughout the entire approach. However, such an approach faced the following implementation challenges.
1.), it was NP-hard, requiring approximation algorithms. 2.) it often resulted in multiple optimal solutions, leading to arbitrary strength assignments. What this means is that if an optimal structure could not be determined wherein the relationship between node c and node b was considered, the node strength would be assigned at random.
The new stuff!
Jumping back to the paper at hand, this paper extends the previous work by proposing a series of Linear Programming (LP) relaxations. The key contributions are as follows:
- Relaxing Integrality Constraints. The first relaxation allows edge strengths to take continuous values between 0 and 1. This not only makes the problem polynomial but also introduces three-level edge strengths—beyond binary distinctions. In doing so, the nuances of the structure can be determined, allowing for future work regarding balanced graph implementations of enemies and friends (you guys remember that stuff? I’m sad it wasn’t on the final, i was good at it ;( )
- Alternative Objective Function Instead of solely maximizing the number of strong edges, the paper suggests maximizing the sum of weights in all triangles. This alternative objective aligns more closely with the empirical distributions of tie strengths in real datasets.
Thus the paper reveals that the proposed LP relaxations have desirable properties. The first relaxation guarantees a half-integral solution, offering a meaningful three-level edge strength assignment. The second one is less obvious: it presents a more accurate view of reality,not everyone is trying to maximize their strong times all along. The countenance for this by the paper allows us to move forward with this information inclusively.
Practical Implications
The experimental evaluation conducted by the authors showcases the strengths of their proposed approach. By relaxing the rigid constraints of STCbinary, the new method adapts better to real-world scenarios, questioning the validity of relying solely on the STC property for edge strength inference.
Conclusions
This paper gives an insight into how the ideas we have talked about in class have continued to develop. I look forward to seeing my kids networks textbook in 20 years, maybe thell have a copy of this new research somewherein it? By leveraging LP relaxations, the approach introduces more flexibility, allowing for a finer-grained inference of edge strengths. Theoretical insights and empirical results suggest that this methodology could be a valuable addition to the toolkit of social network analysts, providing a more realistic portrayal of the intricate fabric of social connections.
Shout out to the professors!
Source:
https://link.springer.com/article/10.1007/s10618-020-00673-0