research-article

LaFT-tree: perceiving the expansion trace of one's circle of friends in online social networks

Authors:

Philip S. YuAuthors Info & Claims

WSDM '13: Proceedings of the sixth ACM international conference on Web search and data mining

Pages 597 - 606

https://doi.org/10.1145/2433396.2433472

Published: 04 February 2013 Publication History

Abstract

Many patterns have been discovered to explain and analyze how people make friends. Among them is the triadic closure, supported by the principle of the transitivity of friendship, which means for an individual the friends of her friend are more likely to become her new friends. However, people's motivations under this principle haven't been well studied, and it's still unknown that how this principle works in diverse situations.

In this paper, we try to study this principle deeply based on the behavior modeling. We study how one expands her egocentric network via her friends, also called intermediaries, based on the transitivity of friendship. We propose LaFT-Tree, a tree-based representation of friendship formation inspired from triadic closure. LaFT-Tree provides a hierarchical view of the flat structure of one's egocentric network by visualizing the expansion trace of one's egocentric network. We model people's friend-making behaviors using LaFT-LDA, a generative model for LaFT-Tree learning.

The proposed model is evaluated on both synthetic and real-world social networks and experimental results demonstrate the effectiveness of LaFT-LDA for LaFT-Tree inference. We also present some interesting applications of the LaFT-Tree, showing that our model can be generalized and benefit other social network analysis tasks.

References

[1]

A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509--512, 1999.

[2]

M. Berlingerio, F. Bonchi, B. O. R. Bringmann, and A. Gionis. Mining graph evolution rules. In ECML PKDD'09, pages 115--130, 2009.

Digital Library

[3]

D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent dirichlet allocation. J. Mach. Learn. Res., 3:993--1022, Mar. 2003.

[4]

M. J. Brzozowski and D. M. Romero. Who should i follow? recommending people in directed social networks. In ICWSM'11, 2011.

[5]

M. De Choudhury. Tie formation on twitter: Homophily and structure of egocentric networks. In SocialCom/PASSAT'11, pages 465--470, 2011.

[6]

M. Doroud, P. Bhattacharyya, S. F. Wu, and D. Felmlee. The evolution of ego-centric triads: A microscopic approach toward predicting macroscopic network properties. In SocialCom/PASSAT'11, pages 172--179, 2011.

[7]

S. A. Golder and S. Yardi. Structural predictors of tie formation in twitter: Transitivity and mutuality. In SocialCom/PASSAT'10, pages 88--95, 2010.

Digital Library

[8]

M. S. Granovetter. The Strength of Weak Ties. The American Journal of Sociology, 78(6):1360--1380, 1973.

[9]

J. Hopcroft, T. Lou, and J. Tang. Who will follow you back?: reciprocal relationship prediction. In CIKM'11, pages 1137--1146, 2011.

Digital Library

[10]

H. Hu and X. Wang. How people make friends in social networking sites - a microscopic perspective. Physica A: Statistical Mechanics and its Applications, 391(4):1877--1886, 2012.

[11]

D. Krackhardt and M. S. Handcock. Heider vs simmel: emergent features in dynamic structures. In Proceedings of the 2006 conference on Statistical network analysis, ICML'06, pages 14--27, 2007.

Digital Library

[12]

R. Kumar, J. Novak, and A. Tomkins. Structure and evolution of online social networks. In KDD'06, pages 611--617, 2006.

Digital Library

[13]

R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. Stochastic models for the web graph. In FOCS'00, pages 57 --65, 2000.

Digital Library

[14]

J. Leskovec, L. Backstrom, R. Kumar, and A. Tomkins. Microscopic evolution of social networks. In KDD'08, pages 462--470, 2008.

Digital Library

[15]

J. Leskovec, J. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data, 1(1), 2007.

Digital Library

[16]

C. W.-k. Leung, E.-P. Lim, D. Lo, and J. Weng. Mining interesting link formation rules in social networks. In CIKM'10, pages 209--218, 2010.

Digital Library

[17]

D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. In CIKM'03, pages 556--559, 2003.

Digital Library

[18]

M. McPherson, L. Smith-Lovin, and J. M. Cook. Birds of a feather: Homophily in social networks. ANNUAL REVIEW OF SOCIOLOGY, 27:415--444, 2001.

[19]

M. E. J. Newman. Clustering and preferential attachment in growing networks. PHYS.REV.E, 64:025102, 2001.

[20]

V.-A. Nguyen, E.-P. Lim, H.-H. Tan, J. Jiang, and A. Sun. Do you trust to get trust? a study of trust reciprocity behaviors and reciprocal trust prediction. In SDM'10, pages 72--83, 2010.

[21]

J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, and M. Hsu. Prefixspan: Mining sequential patterns by prefix-projected growth. In ICDE'01, pages 215--224, 2001.

Digital Library

[22]

A. Rapoport. Spread of information through a population with socio-structural bias: I. assumption of transitivity. Bulletin of Mathematical Biology, 15:523--533, 1953.

[23]

D. M. Romero and J. Kleinberg. The directed closure process in hybrid social-information networks, with an analysis of link formation on twitter. In ICWSM'10, 2010.

[24]

G. Simmel and K. H. Wolff. The Sociology of Georg Simmel. Free Press, 1964.

[25]

D. Yin, L. Hong, and B. D. Davison. Structural link analysis and prediction in microblogs. In CIKM'11, pages 1163--1168, 2011.

Digital Library

Cited By

Wang MGe JZhang DZhang F(2018)An Improved Artificial Immune System Model for Link PredictionPRICAI 2018: Trends in Artificial Intelligence10.1007/978-3-319-97310-4_1(1-9)Online publication date: 27-Jul-2018
https://doi.org/10.1007/978-3-319-97310-4_1
Xue ZLi RLi YHuo LGu XXiao W(2018) FRFB: Top‐ k Followee Recommendation by exploring the Following Behaviors in social networks Concurrency and Computation: Practice and Experience10.1002/cpe.451430:15Online publication date: 25-Jun-2018
https://doi.org/10.1002/cpe.4514
Jia YWang YCheng X(2015)Learning to Predict Links by Integrating Structure and Interaction Information in MicroblogsJournal of Computer Science and Technology10.1007/s11390-015-1563-930:4(829-842)Online publication date: 8-Jul-2015
https://doi.org/10.1007/s11390-015-1563-9
Show More Cited By

Index Terms

LaFT-tree: perceiving the expansion trace of one's circle of friends in online social networks
1. Applied computing
  1. Law, social and behavioral sciences
    1. Sociology
2. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Learning latent friendship propagation networks with interest awareness for link prediction
SIGIR '13: Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval

It's well known that the transitivity of friendship is a popular sociological principle in social networks. However, it's still unknown that to what extent people's friend-making behaviors follow this principle and to what extent it can benefit the link ...
LAFT-Explorer: inferring, visualizing and predicting how your social network expands
KDD '13: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining

The study of social network evolution has attracted many attentions from both the industry and academia. In this paper we demonstrate LaFT-Explorer, a general toolkit for explaining and reproducing the network growth process based on the friendship ...
Large-scale social recommender systems: challenges and opportunities
WWW '13 Companion: Proceedings of the 22nd International Conference on World Wide Web

Online social networks have become very important for networking, communication, sharing, and content discovery. Recommender systems play a significant role on any online social network for engaging members, recruiting new members, and recommending ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

WSDM '13: Proceedings of the sixth ACM international conference on Web search and data mining

February 2013

816 pages

ISBN:9781450318693

DOI:10.1145/2433396

General Chairs:
Stefano Leonardi
Sapienza University of Rome, Italy
,
Alessandro Panconesi
Sapienza University of Rome, Italy
,
Program Chairs:
Paolo Ferragina
University of Pisa, Italy
,
Aristides Gionis
Yahoo! Research, Barcelona, Spain

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 February 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

WSDM 2013

Sponsor:

WSDM 2013: Sixth ACM International Conference on Web Search and Data Mining

February 4 - 8, 2013

Rome, Italy

Acceptance Rates

Overall Acceptance Rate 498 of 2,863 submissions, 17%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
256
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang MGe JZhang DZhang F(2018)An Improved Artificial Immune System Model for Link PredictionPRICAI 2018: Trends in Artificial Intelligence10.1007/978-3-319-97310-4_1(1-9)Online publication date: 27-Jul-2018
https://doi.org/10.1007/978-3-319-97310-4_1
Xue ZLi RLi YHuo LGu XXiao W(2018) FRFB: Top‐ k Followee Recommendation by exploring the Following Behaviors in social networks Concurrency and Computation: Practice and Experience10.1002/cpe.451430:15Online publication date: 25-Jun-2018
https://doi.org/10.1002/cpe.4514
Jia YWang YCheng X(2015)Learning to Predict Links by Integrating Structure and Interaction Information in MicroblogsJournal of Computer Science and Technology10.1007/s11390-015-1563-930:4(829-842)Online publication date: 8-Jul-2015
https://doi.org/10.1007/s11390-015-1563-9
Zhang JWang CWang JYu J(2014)Inferring continuous dynamic social influence and personal preference for temporal behavior predictionProceedings of the VLDB Endowment10.14778/2735508.27355168:3(269-280)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.14778/2735508.2735516
Zhang JWang CWang JChung CBroder AShim KSuel T(2014)Who proposed the relationship?Proceedings of the 23rd international conference on World wide web10.1145/2566486.2567968(807-818)Online publication date: 7-Apr-2014
https://dl.acm.org/doi/10.1145/2566486.2567968
Zhang JWang CNing YLiu YWang JYu PGrossman RUthurusamy RDhillon IKoren Y(2013)LAFT-ExplorerProceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining10.1145/2487575.2487702(1510-1513)Online publication date: 11-Aug-2013
https://dl.acm.org/doi/10.1145/2487575.2487702
Zhang JWang CYu PWang JJones GSheridan PKelly Dde Rijke MSakai T(2013)Learning latent friendship propagation networks with interest awareness for link predictionProceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval10.1145/2484028.2484029(63-72)Online publication date: 28-Jul-2013
https://dl.acm.org/doi/10.1145/2484028.2484029
Tanbeer SJiang FLeung CMacKinnon RMedina I(2013)Finding groups of friends who are significant across multiple domains in social networks2013 Fifth International Conference on Computational Aspects of Social Networks10.1109/CASoN.2013.6622608(21-26)Online publication date: Aug-2013
https://doi.org/10.1109/CASoN.2013.6622608

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents