Ph.D. Theses

Ranking Models to Identify Influential Actors in Large Scale Social Networks

By Xiaohui Lu
Advisor: Sibel Adali
June 5, 2013

One of the primary task of social network analysis is the identification of the "important" or "prominent" actors in a social network. Centrality measures based on one's structural position, such as betweenness, closeness and degree centrality, are widely applied to various social networks for this purpose. However, these measures often suffer from prohibitive computational cost, non-intuitive assumptions, and limited applications. Meanwhile, with the explosive emergence and the widespread accessibility of online social network sites, large scale networks with multiple types of entities, such as author-publication, actor-movie, employee-email networks, are ubiquitous and readily available. However, due to size and multiple modes, centrality measures are helpless in such networks.

In this thesis, we develop a framework to identify prominent actors from several perspectives. We first investigate the importance of actors in actor-actor networks. In these networks, centrality algorithms are good candidates. However, these centrality measures suffer from several issues - they either look solely at the structure of the network disregarding issues like attention nodes have to give to others or make a shortest path interaction assumption that might be impractical in large networks. To address these issues, we develop two algorithms "Attentive Betweenness Centrality (ABC)" and "Attentive Closeness Centrality (ACC)". These two algorithms take multiple paths of information flow and attention into consideration while computing importance scores of actors. ABC reduces anomalous behaviors of classical betweenness centrality while captures its essence. ACC, on the other hand, targets the improvement of closeness. These two algorithms have high performance in identifying prominent actors.

In many cases, algorithms for pure actor-actor networks are not able to take advantage of abundant information hidden in multi-mode (heterogeneous) networks. We develop an algorithm to analyze such heterogeneous networks - "iterative Hyperedge Ranking (iHypR)". As the name implies, the algorithm iterates from one type of objects to another, and importance of objects flow through these different types of edges. This algorithm is based on empirical observations - prominent actors are likely to collaborate with prominent others; good collaboration product tends to be in good groups.

The aforementioned algorithms are very different in methodology, however, they have one point in common - ranking actors globally. In the third model, we look at individual centrality in one's own community and the community centrality. We develop methods to compute prominence of individuals as a function of their position in their own communities and the importance of their communities in the network. We illustrate with many real life social networks that the algorithms in this thesis improve on the state of the art in computing prominence by incorporating different network levels of information.

Return to main PhD Theses page