Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

10-2010

Abstract

Link structures are important patterns one looks out for when modeling and analyzing social networks. In this paper, we propose the task of mining interesting Link Formation rules (LF-rules) containing link structures known as Link Formation patterns (LF-patterns). LF-patterns capture various dyadic and/or triadic structures among groups of nodes, while LF-rules capture the formation of a new link from a focal node to another node as a postcondition of existing connections between the two nodes. We devise a novel LF-rule mining algorithm, known as LFR-Miner, based on frequent subgraph mining for our task. In addition to using a support-confidence framework for measuring the frequency and signi¯cance of LF-rules, we introduce the notion of expected support to account for the extent to which LF- rules exist in a social network by chance. Specifically, only LF-rules with higher-than-expected support are considered interesting. We conduct empirical studies on two real-world social networks, namely Epinions and myGamma. We report interesting LF-rules mined from the two networks, and compare our findings with earlier findings in social network analysis.

Keywords

Social network analysis, Local structures, Frequent subgraph mining, social networks

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing | Social Media

Publication

CIKM'10: Proceedings of the 19th ACM International Conference on Information and Knowledge Management: October 26-30, 2010, Toronto

First Page

209

Last Page

218

ISBN

9781450300995

Identifier

10.1145/1871437.1871468

Publisher

ACM

City or Country

New York

Additional URL

http://doi.org/10.1145/1871437.1871468

Download

Share

COinS