Towards scalable X10 based link prediction for large scale social networks

Abstract

The use of social application such as Twitter or FaceBook becomes popular in recent years. In particular, Twitter in- creases the number of the users rapidly from 2009 as the place that users can tweet anything in 140 characters. In the area of social network analysis, the user network of Twitter is frequently analyzed. Haewoon, et.al.,[4] ana- lyzed the Twitter user network from various point of view in 2009, and they show that the Twitter user network has some different feature from conventional social networks. Bong- won, et.al., also made a collection of 74 millions tweets in 2010, and investigated the influence that "retweet" gives for diffusion of the information. Such analysis not only reveal the unique characteristics of Twitter user network, but also make some networking service such as finding users who are similar to someone, or the recommendation of commodities by using tweet information. There are some analysis such as clustering which needs en- Tire data of the network. However, since social networks are increasing day by day, it becomes impossible to obtain the entire network by crawling. As a solution of this problem, there is the network analysis called link prediction. This enables to predict true network from a given part of the network. If we use link prediction, we can recover the entire network from the network data which we already obtained, and apply some analysis such as clustering to predicted net- work, then we may get the approximate result of the analysis for the entire network. In our research, we implemented one of the link prediction algorithm named Link Propagation in X10, which is a par- Allel programming language. And evaluated its scalability and precision with Twitter user network data.