Detecting Strong Ties Using Network Motifs

Abstract

Detecting strong ties among users in social and information networks is a fundamental operation that can improve performance on a multitude of personalization and ranking tasks. Strong-tie edges are often readily obtained from the social network as users often participate in multiple overlapping networks via features such as following and messaging. These networks may vary greatly in size, density and the information they carry. This setting leads to a natural strong tie detection task: given a small set of labeled strong tie edges, how well can one detect unlabeled strong ties in the remainder of the network? This task becomes particularly daunting for the Twitter network due to scant availability of pairwise relationship attribute data, and sparsity of strong tie networks such as phone contacts. Given these challenges, a natural approach is to instead use structural network features for the task, produced by {\em combining} the strong and "weak" edges. In this work, we demonstrate via experiments on Twitter data that using only such structural network features is sufficient for detecting strong ties with high precision. These structural network features are obtained from the presence and frequency of small network motifs on combined strong and weak ties. We observe that using motifs larger than triads alleviate sparsity problems that arise for smaller motifs, both due to increased combinatorial possibilities as well as benefiting strongly from searching beyond the ego network. Empirically, we observe that not all motifs are equally useful, and need to be carefully constructed from the combined edges in order to be effective for strong tie detection. Finally, we reinforce our experimental findings with providing theoretical justification that suggests why incorporating these larger sized motifs as features could lead to increased performance in planted graph models.

To appear in Proceedings of WWW 2017 (Web-science track)

References in corpus (5)

• Spectral redemption: clustering sparse networks
• Triadic Measures on Graphs: The Power of Wedge Sampling
• Romantic Partnerships and the Dispersion of Social Ties: A Network Analysis of Relationship Status on Facebook
• Modeling Social Networks with Node Attributes using the Multiplicative Attribute Graph Model
• Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections

Cited by in corpus (13)

• Data-driven Computational Social Science: A Survey
• Subgraph Networks with Application to Structural Feature Space Expansion
• The Power of Pivoting for Exact Clique Counting
• Motif-based Convolutional Neural Network on Graphs
• Interplay between Topology and Edge Weights in Real-World Graphs: Concepts, Patterns, and an Algorithm
• Efficiently Counting Vertex Orbits of All 5-vertex Subgraphs, by EVOKE
• Motif Enhanced Recommendation over Heterogeneous Information Network
• Discourse Analysis of Covid-19 in Persian Twitter Social Networks Using Graph Mining and Natural Language Processing
• NEW: A Generic Learning Model for Tie Strength Prediction in Networks
• Consistent recovery threshold of hidden nearest neighbor graphs
• Pattern Morphing for Efficient Graph Mining
• Ranking Users in Social Networks with Motif-based PageRank
• Tie Strength in Online Social Networks and its Applications: A Brief Study