Neighborhood Skyline on Graphs: Concepts, Algorithms and Applications

Neighborhood inclusion, representing that all the neighbors of a vertex are also adjacent to another vertex, has been recognized as an important relationship between two vertices in a graph. We call a vertex u dominating v, denoted by v ≤ u, if N(v) ⊆ N(u) ∪ {u} holds, where (v) denotes the set of neighbors of v. Based on such a domination relationship, we propose a concept called neighborhood skyline. The neighborhood skyline is a set of vertices in which any vertex u cannot be dominated by the other nodes in the graph G, i.e., ∄ v ∈ G,u ≤ v. We study a new problem, called neighborhood skyline computation, and develop a filter-refine search framework, FilterRefineSky, to efficiently find the neighborhood skyline by searching the vertices in a small candidate set instead of in the entire graph. We show that our neighborhood skyline technique can be used to speed up the computation of two well-studied group centrality maximization problems and the maximum clique search problem in graphs. Extensive experimental studies conducted on five large real-life datasets demonstrate the effectiveness of neighborhood skyline, and the efficiency and scalability of our algorithms.