A relation context oriented approach to identify strong ties in social networks

Strong ties play a crucial role in transmitting sensitive information in social networks, especially in the criminal justice domain. However, large social networks containing many entities and relations may also contain a large amount of noisy data. Thus, identifying strong ties accurately and efficiently within such a network poses a major challenge. This paper presents a novel approach to address the noise problem. We transform the original social network graph into a relation context-oriented edge-dual graph by adding new nodes to the original graph based on abstracting the relation contexts from the original edges (relations). Then we compute the local k-connectivity between two given nodes. This produces a measure of the robustness of the relations. To evaluate the correctness and the efficiency of this measure, we conducted an implementation of a system which integrated a total of 450 GB of data from several different data sources. The discovered social network contains 4,906,460 nodes (individuals) and 211,403,212 edges. Our experiments are based on 700 co-offenders involved in robbery crimes. The experimental results show that most strong ties are formed with k >= 2. (C) 2011 Elsevier B.V. All rights reserved.