A method for identifying friend relationship in one or more on-line social networks includes creating a graph representing friend relationships among multiple participants of the social networks, in which the nodes of the graph represent the participants and each edge of the graph represents an existing friend relationship in the social networks between two of the participants. The resulting graph is then analyzed using, for example, a graph-theoretical technique to identify pairs of nodes that are unconnected in the graph. A score is then assigned between each identified pair of nodes. The score represents the likelihood that the participants corresponding to the identified pair of nodes are real life friends. The score for each identified pair may be computed based on the connectedness of a subgraph of the graph that includes the identified pair of nodes. One example of such a subgraph is a 4-node subgraph. The score may be computed based on the number of nodes connected to each node in the identified pair, or a variety of factors (e.g., profile information of the participants), in which each factor is provided a weight reflecting the contribution of the factor relative to the other factors. The weights may be adaptive. In one implementation, the graph is built based on collecting subgraphs of friend relationships for each participant, one participant at a time.
展开▼
