A Structural Approach for Finding Real-Friend Links in Internet Social Networks

We propose a method of structural analysis for detecting true/false friend links in Internet social networks. By the balance theory in social science and observed user behaviors, we define two graph optimization problems - One can be solved in polynomial time while the other is NP-hard. Exact and heuristic algorithms are proposed for the NP-hard problem. To show the efficiency of the algorithm, experiments on random graphs were performed. More importantly, to show the effectiveness of the new model, experiments were performed on random graphs which simulate the behavior on Internet social networks. By examining the precisions and recalls of both true and false edges, it is shown that our algorithms are efficient for moderate data and the new models are effective.