Finding Large Diverse Communities on Networks: The Edge-Maximum k*-Partite Clique

In this work we examine the problem of finding large, diverse communities on graphs where the users are separated into distinct groups. More specifically, this work considers diversity to be the inclusion of users from multiple groups as opposed to homogeneous communities in which the majority of users are from one group. We design and propose the k*-Partite Clique (and the edge-maximum k*-Partite Clique Problem) which modifies the k-Partite Clique structure as a means to capture these large, diverse communities in a way that does not currently exist. We then design a non-trivial baseline enumeration algorithm, which is further improved via heuristics to significantly reduce the running time whilst avoiding excessive memory requirements. Moreover, we propose a core as well as a truss structure for the k-Partite environment aimed at finding the edge-maximum k*-Partite Clique structure on the network. Comprehensive experiments on real-world datasets verify both the effectiveness of the k*-Partite Clique at finding diverse communities as well as the efficiency of the proposed heuristics to our algorithms compared to reasonable baselines.