Reverse centrality queries in complex networks

The increasing availability of complex network data from social networks and other sources provides new opportunities for exploration and analysis. In this thesis, we introduce the reverse centrality query, a novel query for complex networks. For a query node q, the reverse centrality query returns a locally maximal induced subgraph R, where q ? R, such that q dominates R according to a centrality index C. Many centrality indices have been introduced to describe the relationships between nodes in complex networks. We focus on degree, graph, and closeness centrality indices and their respective reverse graph centrality queries. The theoretical properties of these queries, together with heuristic variants, are explored. Algorithms for solving these queries are given and experimental results are provided on three real world datasets. The experiments demonstrate reverse centrality queries to be a useful tool for social network analysis.