Cohesive subgraph mining on attributed graphs is a fundamental problem in graph data analysis. Existing cohesive subgraph mining algorithms on attributed graphs do not consider thefairnessof attributes in the subgraph. In this article, we, for the first time, introduce fairness into the widely-used clique model to mine fairness-aware cohesive subgraphs. In particular, we propose three novel fairness-aware maximal clique models on attributed graphs, called weak fair clique, strong fair clique and relative fair clique, respectively. To enumerate all weak fair cliques, we develop an efficient backtracking algorithm called$\mathsf{WFCEnum}$equipped with a novel colorful$k$-core based pruning technique. We also propose an efficient enumeration algorithm called$\mathsf{SFCEnum}$to find all strong fair cliques based on a new attribute-alternatively-selection search technique. To further improve the efficiency, we also present several non-trivial ordering techniques for both weak and strong fair clique enumerations. To enumerate all relative fair cliques, we design an enhanced colorful$k$-core based pruning technique for 2D attributes, and develop two efficient search algorithms:$\mathsf{RFCRefineEnum}$and$\mathsf{RFCAlterEnum}$for arbitrary dimension attributes. The results of extensive experiments on four real-world graphs demonstrate the efficiency, scalability and effectiveness of the proposed algorithms.

Cohesive sub graph mining on attributed graphs is a fundamental problem in graph data analysis. Existing cohesive sub graph mining algorithms on attributed graphs do not consider the fairness of attributes in the subgraph. In this paper, we for the first time introduce fairness into the widely-used clique model to mine fairness-aware cohesive subgraphs. In particular, we propose two novel fairness-aware maximal clique models on attributed graphs, called weak fair clique and strong fair clique respectively. To enumerate all weak fair cliques, we develop an efficient backtracking algorithm called WFCEnum equipped with a novel colorful k-core based pruning technique. We also propose an efficient enumeration algorithm called SFCEnum to find all strong fair cliques based on a new attribute-alternatively-selection search technique. To further improve the efficiency, we also present several non-trivial ordering techniques for both weak and strong fair clique enumeration. The results of extensive experiments on four real-world graphs demonstrate the efficiency and effectiveness of the proposed algorithms.

Betweenness centrality, measured by the number of times a vertex occurs on all shortest paths of a graph, has been recognized as a key indicator for the importance of a vertex in the network. However, the betweenness of a vertex is often very hard to compute because it needs to explore all the shortest paths between the other vertices. Recently, a relaxed concept called ego-betweenness was introduced which focuses on computing the betweenness of a vertex in its ego network. In this work, we study a problem of finding the top-k vertices with the highest ego-betweennesses. We first develop two novel search algorithms equipped with a basic upper bound and a dynamic upper bound to efficiently solve this problem. Then, we propose local-update and lazy-update solutions to maintain the ego-betweennesses for all vertices and the top-k results when the graph is updated by an edge insertion and deletion, respectively. In addition, we also present two efficient parallel algorithms to further improve the efficiency. The results of extensive experiments on five large real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.