Directed Social Network Simplification Based On Information Spread

Social Network is one of the most important features of WEB 2.0 era. On one hand, it expands the function of traditional world wide web. On the other hand, it improves the enthusiasm of users to participate and construct the web. It provides novel ways for users to interact with each other and has deeply influence the habit of people all over the world. Twitter is a typical social network. The most important feature in Twitter is that the information spreads very fast and the feature owes to the mechanism of retweet that twitter offers. The basic procedure is that every user could retweet any tweet in the network and the tweet can be received by the followers of the user. Thus, once a few users retweet some specific tweets, the tweets could spread to a wide range very fast. Twitter implements the retweet mechanism very graceful. It ensures that one tweet could be spread at most once to a user. This mechanism takes some indistinct problems to network analyze. User sorting is one of the topics that is influenced. At the time most user sorting methods are based on Page Rank. This methods could construct a network based on the users relation and assume that information could spread along any relation. However, it violate the mechanism twitter offers. As far, we havn't seen any related work, while this issue is deserved research.This paper is the first to research retweet mechanism, analyze the features, define the problem, and give the algorithm at last. We can say that this work build a solid and correct foundation for other social network analyze. The paper starts from the retweet mechanism, define the network simplification problem, give the algorithm based on the spread triangle, and optimize the algorithm. In order to extend the application scenarios, we have built a prototype system. The system could visualize the graph and demonstrate the effect of graph simplification.