Advanced search
1 file | 597.48 KB
Author
Organization
Project
PARIS project is part of the SBO Program of the IWT (IWT-SBO-Nr. 110067)
Abstract
Nodes of a social graph often represent entities with specific labels, denoting properties such as age-group or gender. Design of algorithms to assign labels to unlabeled nodes by leveraging node-proximity and a-priori labels of seed nodes is of significant interest. A semi-supervised approach to solve this problem is termed ``LPA-Label Propagation Algorithm'' where labels of a subset of nodes are iteratively propagated through the network to infer yet unknown node labels. While LPA for node labelling is extremely fast and simple, it works well only with an assumption of node-homophily -- connected nodes are connected because they must deserve a similar label -- which can often be a misnomer. In this paper we propose a novel algorithm ``Adaptive Label Propagation'' that dynamically adapts to the underlying characteristics of homophily, heterophily, or otherwise, of the connections of the network, and applies suitable label propagation strategies accordingly. Moreover, our adaptive label propagation approach is scalable as demonstrated by its implementation in Grappa, a distributed shared-memory system. Our experiments on social graphs from Facebook, YouTube, Live Journal, Orkut and Netlog demonstrate that our approach not only improves the labelling accuracy but also computes results for millions of users within a few seconds.

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 597.48 KB

Citation

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

Chicago
Farnadi, Golnoosh, Zeinab Mahdavifar, Ivan Keller, Jacob Nelson, Ankur Teredesai, Marie-Francine Moens, and Martine De Cock. 2015. “Scalable Adaptive Label Propagation in Grappa.” In Proceedings 2015 IEEE International Conference on Big Data, ed. H Ho, BC Ooi, MJ Zaki, XH Hu, L Haas, V Kumar, S Rachuri, et al., 1485–1491. New York, NY, USA: IEEE.
APA
Farnadi, G., Mahdavifar, Z., Keller, I., Nelson, J., Teredesai, A., Moens, M.-F., & De Cock, M. (2015). Scalable adaptive label propagation in Grappa. In H. Ho, B. Ooi, M. Zaki, X. Hu, L. Haas, V. Kumar, S. Rachuri, et al. (Eds.), Proceedings 2015 IEEE international conference on big data (pp. 1485–1491). Presented at the IEEE International conference on Big Data , New York, NY, USA: IEEE.
Vancouver
1.
Farnadi G, Mahdavifar Z, Keller I, Nelson J, Teredesai A, Moens M-F, et al. Scalable adaptive label propagation in Grappa. In: Ho H, Ooi B, Zaki M, Hu X, Haas L, Kumar V, et al., editors. Proceedings 2015 IEEE international conference on big data. New York, NY, USA: IEEE; 2015. p. 1485–91.
MLA
Farnadi, Golnoosh, Zeinab Mahdavifar, Ivan Keller, et al. “Scalable Adaptive Label Propagation in Grappa.” Proceedings 2015 IEEE International Conference on Big Data. Ed. H Ho et al. New York, NY, USA: IEEE, 2015. 1485–1491. Print.
@inproceedings{7100103,
  abstract     = {Nodes of a social graph often represent entities with specific labels, denoting properties such as age-group or gender. Design of algorithms to assign labels to unlabeled nodes by leveraging node-proximity and a-priori labels of seed nodes is of significant interest. A semi-supervised approach to solve this problem is termed ``LPA-Label Propagation Algorithm'' where labels of a subset of nodes are iteratively propagated through the network to infer yet unknown node labels. While LPA for node labelling is extremely fast and simple, it works well only with an assumption of node-homophily -- connected nodes are connected because they must deserve a similar label -- which can often be a misnomer. In this paper we propose a novel algorithm ``Adaptive Label Propagation'' that dynamically adapts to the underlying characteristics of homophily, heterophily, or otherwise, of the connections of the network, and applies suitable label propagation strategies accordingly. Moreover, our adaptive label propagation approach is scalable as demonstrated by its implementation in Grappa, a distributed shared-memory system. Our experiments on social graphs from Facebook, YouTube, Live Journal, Orkut and Netlog demonstrate that our approach not only improves the labelling accuracy but also computes results for millions of users within a few seconds.},
  author       = {Farnadi, Golnoosh and Mahdavifar, Zeinab and Keller, Ivan and Nelson, Jacob and Teredesai, Ankur and Moens, Marie-Francine and De Cock, Martine},
  booktitle    = {Proceedings 2015 IEEE international conference on big data},
  editor       = {Ho, H and Ooi, BC and Zaki, MJ and Hu, XH and Haas, L and Kumar, V and Rachuri, S and Yu, SP and Hsiao, MHI and Li, J and Luo, F and Pyne, S and Ogan, K},
  isbn         = {9781479999255},
  language     = {eng},
  location     = {Santa Clara, CA, USA},
  pages        = {1485--1491},
  publisher    = {IEEE},
  title        = {Scalable adaptive label propagation in Grappa},
  year         = {2015},
}

Web of Science
Times cited: