LinkProbe: Probabilistic inference on large-scale social networks

Haiquan Chen, Wei Shinn Ku, Haixun Wang, Liang Tang, Min Te Sun

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

11 Scopus citations


As one of the most important Semantic Web applications, social network analysis has attracted more and more interest from researchers due to the rapidly increasing availability of massive social network data. A desired solution for social network analysis should address the following issues. First, in many real world applications, inference rules are partially correct. An ideal solution should be able to handle partially correct rules. Second, applications in practice often involve large amounts of data. The inference mechanism should scale up towards large-scale data. Third, inference methods should take into account probabilistic evidence data because these are domains abounding with uncertainty. Various solutions for social network analysis have existed for quite a few years; however, none of them support all the aforementioned features. In this paper, we design and implement LinkProbe, a prototype to quantitatively predict the existence of links among nodes in large-scale social networks, which are empowered by Markov Logic Networks (MLNs). MLN has been proved to be an effective inference model which can handle complex dependencies and partially correct rules. More importantly, although MLN has shown acceptable performance in prior works, it is also reported as impractical in handling large-scale data due to its highly demanding nature in terms of inference time and memory consumption. In order to overcome these limitations, LinkProbe retrieves the κ-backbone graphs and conducts the MLN inference on both the most globally influencing nodes and most locally related nodes. Our extensive experiments show that LinkProbe manages to provide a tunable balance between MLN inference accuracy and inference efficiency.

Original languageEnglish
Title of host publicationICDE 2013 - 29th International Conference on Data Engineering
Number of pages12
StatePublished - 2013
Event29th International Conference on Data Engineering, ICDE 2013 - Brisbane, QLD, Australia
Duration: 8 Apr 201311 Apr 2013

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627


Conference29th International Conference on Data Engineering, ICDE 2013
CityBrisbane, QLD


Dive into the research topics of 'LinkProbe: Probabilistic inference on large-scale social networks'. Together they form a unique fingerprint.

Cite this