Advanced search
1 file | 838.02 KB Add to list

Relaxing the strong triadic closure problem for edge strength inference

Author
Organization
Abstract
Social networks often provide only a binary perspective on social ties: two individuals are either connected or not. While sometimes external information can be used to infer the strength of social ties, access to such information may be restricted or impractical to obtain. Sintos and Tsaparas (KDD 2014) first suggested to infer the strength of social ties from the topology of the network alone, by leveraging the Strong Triadic Closure (STC) property. The STC property states that if person A has strong social ties with persons B and C, B and C must be connected to each other as well (whether with a weak or strong tie). They exploited this property to formulate the inference of the strength of social ties as a NP-hard maximization problem, and proposed two approximation algorithms. We refine and improve this line of work, by developing a sequence of linear relaxations of the problem, which can be solved exactly in polynomial time. Usefully, these relaxations infer more fine-grained levels of tie strength (beyond strong and weak), which also allows one to avoid making arbitrary strong/weak strength assignments when the network topology provides inconclusive evidence. Moreover, these relaxations allow us to easily change the objective function to more sensible alternatives, instead of simply maximizing the number of strong edges. An extensive theoretical analysis leads to two efficient algorithmic approaches. Finally, our experimental results elucidate the strengths of the proposed approach, while at the same time questioning the validity of leveraging the STC property for edge strength inference in practice.
Keywords
VERTEX COVER, ALGORITHMS, TIES, SET, Strong triadic closure, Strength of social ties, Linear programming, Convex relaxations, Half-integrality

Downloads

  • DS307.pdf
    • full text (Published version)
    • |
    • open access
    • |
    • PDF
    • |
    • 838.02 KB

Citation

Please use this url to cite or link to this publication:

MLA
Adriaens, Florian, et al. “Relaxing the Strong Triadic Closure Problem for Edge Strength Inference.” DATA MINING AND KNOWLEDGE DISCOVERY, vol. 34, 2020, pp. 611–51.
APA
Adriaens, F., De Bie, T., Gionis, A., Lijffijt, J., Matakos, A., & Rozenshtein, P. (2020). Relaxing the strong triadic closure problem for edge strength inference. DATA MINING AND KNOWLEDGE DISCOVERY, 34, 611–651.
Chicago author-date
Adriaens, Florian, Tijl De Bie, Aristides Gionis, Jefrey Lijffijt, Antonis Matakos, and Polina Rozenshtein. 2020. “Relaxing the Strong Triadic Closure Problem for Edge Strength Inference.” DATA MINING AND KNOWLEDGE DISCOVERY 34: 611–51.
Chicago author-date (all authors)
Adriaens, Florian, Tijl De Bie, Aristides Gionis, Jefrey Lijffijt, Antonis Matakos, and Polina Rozenshtein. 2020. “Relaxing the Strong Triadic Closure Problem for Edge Strength Inference.” DATA MINING AND KNOWLEDGE DISCOVERY 34: 611–651.
Vancouver
1.
Adriaens F, De Bie T, Gionis A, Lijffijt J, Matakos A, Rozenshtein P. Relaxing the strong triadic closure problem for edge strength inference. DATA MINING AND KNOWLEDGE DISCOVERY. 2020;34:611–51.
IEEE
[1]
F. Adriaens, T. De Bie, A. Gionis, J. Lijffijt, A. Matakos, and P. Rozenshtein, “Relaxing the strong triadic closure problem for edge strength inference,” DATA MINING AND KNOWLEDGE DISCOVERY, vol. 34, pp. 611–651, 2020.
@article{8645318,
  abstract     = {Social networks often provide only a binary perspective on social ties: two individuals are either connected or not. While sometimes external information can be used to infer the strength of social ties, access to such information may be restricted or impractical to obtain. Sintos and Tsaparas (KDD 2014) first suggested to infer the strength of social ties from the topology of the network alone, by leveraging the Strong Triadic Closure (STC) property. The STC property states that if person A has strong social ties with persons B and C, B and C must be connected to each other as well (whether with a weak or strong tie). They exploited this property to formulate the inference of the strength of social ties as a NP-hard maximization problem, and proposed two approximation algorithms. We refine and improve this line of work, by developing a sequence of linear relaxations of the problem, which can be solved exactly in polynomial time. Usefully, these relaxations infer more fine-grained levels of tie strength (beyond strong and weak), which also allows one to avoid making arbitrary strong/weak strength assignments when the network topology provides inconclusive evidence. Moreover, these relaxations allow us to easily change the objective function to more sensible alternatives, instead of simply maximizing the number of strong edges. An extensive theoretical analysis leads to two efficient algorithmic approaches. Finally, our experimental results elucidate the strengths of the proposed approach, while at the same time questioning the validity of leveraging the STC property for edge strength inference in practice.},
  author       = {Adriaens, Florian and De Bie, Tijl and Gionis, Aristides and Lijffijt, Jefrey and Matakos, Antonis and Rozenshtein, Polina},
  issn         = {1384-5810},
  journal      = {DATA MINING AND KNOWLEDGE DISCOVERY},
  keywords     = {VERTEX COVER,ALGORITHMS,TIES,SET,Strong triadic closure,Strength of social ties,Linear programming,Convex relaxations,Half-integrality},
  language     = {eng},
  pages        = {611--651},
  title        = {Relaxing the strong triadic closure problem for edge strength inference},
  url          = {http://dx.doi.org/10.1007/s10618-020-00673-0},
  volume       = {34},
  year         = {2020},
}

Altmetric
View in Altmetric
Web of Science
Times cited: