With Anchors or Not: Fairness-Aware Truss-Based Community Search on Attributed Graphs

Community search, which finds cohesive subgraphs containing given query vertices, has attracted much attention in decades. On attributed graphs, when considering the fairness of members' attributes in a community, the cohesiveness constraint of a clique is too strong, which often causes no fair clique based communities can be found. Thus, in this paper, we use the k-truss model, which is a relaxation of the clique but whose members have large engagement and high tie strength, to describe fair communities, namely fair k-truss communities (FTC) and anchored fair k-truss communities (AFTC, using anchored vertices to help satisfying the fairness constraint). We formulate the FTC and AFTC search problems to find the FTC or AFTC containing a given query vertex$q$which has the largest$k$and the smallest diameter. We prove the hardness of both problems. We develop several greedy algorithms and acceleration strategies to solve FTC and AFTC search problems. Experiments on 8 real-world networks show the significance of our FTC and AFTC models, and high performance of our algorithms and acceleration strategies.