Identification of key separators in a social network

Social Networking is one of the fastest growing phenomena in today’s Internet world. Its popularity has led to a huge amount of data that contain hidden characteristics of societies, behavioral patterns and different roles of individuals in the network. Such information can be used in various ways including advertising, marketing, or assisting decision-makings to improve efficiency in social interactions, e.g., dissemination of information for disastrous prevention or emergencies. As social networking is more integrated to our daily lives, the ability to automatically analyze and extract useful information from social network data becomes increasingly more important. The problem of identifying sets of key players in a social network has been intensively studied. By quantifying structural importance of a graph representing communications among participants (players) of a social network, various approaches, using a variety of measures, have been proposed including identification of node centrality, cores, peripherals and social capitals that influence individual players. However, most of these existing techniques do not accurately articulate or make clear distinctions of the real meaning of their measures. This makes it difficult to evaluate and compare the effectiveness of different approaches. A recent study has focused on two fundamental issues of the Key Player Problem (KPP), namely the Key Player Problem-Positive (KPP-POS) and the Key Player Problem-Negative (KPP-NEG). The former searches for players who are in most important positions to quickly diffuse (and receive) information, attitudes or influences, while the latter, the KPP-NEG finds the most important players who hold the network together. Without them, the network will break into fragments. Finding key players for the KPP-POS requires measures of the degrees of connectivity and centrality of a player. Many classic measures have been proposed. However, finding key players for the KPP-NEG is not quite straightforward because it requires a measurement of the reduction in cohesiveness of the network that would result in the absence of a player. Thus, the
problem is defined in a negative mode to reflect the removal of the player before his importance in keeping the network intact can be measured. This thesis addresses the KPP-NEG. We refer to the key players for the KPP-NEG, key separators. Removal of key separators results in network disruption, particularly, fragmentation. This thesis investigates existing measures and algorithms and shows that they do not optimally solve the KPP-NEG as defined. Furthermore, computational aspects of existing approaches are often ignored. Specifically, the thesis examines top three representative measures of key separators: the entropy-based, the distance-based and the betweenness-based approaches, the last of which can be extremely expensive to compute. The main contributions of this thesis include: (1) a new measure for accurately identifying key separators in a social network, (2) complexity analysis of the computation required for the proposed measure compared with those of the three existing approaches, and (3) a proposed method for efficient computation of the betweenness-based approach. The thesis empirically evaluates the proposed measure and compares its correctness and performance on both real-world and simulated social network data sets.