Clique, as a tightly connected subgraph, is a basic model in graph analysis. With the emergence of various graph data, such as weighted attributed graphs, vertices with higher weights have greater influence in clique. However, existing studies often neglect vertex weights in such graphs. To address this gap while ensuring both cohesion and fairness of the clique, we propose a new model called the maximum weight relative fair clique. Specifically, given a weighted attributed graph G and an integer \(\delta \) , an induced subgraph S is a relative fair clique if the difference in the number of vertices in S with any two different attributes is less than or equal to \(\delta \) . And there is no supergraph of S satisfying the above condition. Furthermore, S is a maximum weight relative fair clique if it is a relative fair clique and the total weight of its vertices exceeds that of any other relative fair clique in G. To solve this problem, we first propose a method based on greedy coloring and attribute analysis. We construct optimal tables for all possible subsets to further improve the accuracy. Using these tables, we develop the OPT algorithm and a search algorithm to find the maximum weight relative fair clique in the graph. Extensive experiments on four real-world datasets validate the performance of the proposed algorithm.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Maximum Weight Relative Fair Clique Computation in Attributed Graphs

  • Yijia Mi,
  • Yongye Li,
  • Yufeng Zhang,
  • Chen Chen,
  • Ying Zhang

摘要

Clique, as a tightly connected subgraph, is a basic model in graph analysis. With the emergence of various graph data, such as weighted attributed graphs, vertices with higher weights have greater influence in clique. However, existing studies often neglect vertex weights in such graphs. To address this gap while ensuring both cohesion and fairness of the clique, we propose a new model called the maximum weight relative fair clique. Specifically, given a weighted attributed graph G and an integer \(\delta \) , an induced subgraph S is a relative fair clique if the difference in the number of vertices in S with any two different attributes is less than or equal to \(\delta \) . And there is no supergraph of S satisfying the above condition. Furthermore, S is a maximum weight relative fair clique if it is a relative fair clique and the total weight of its vertices exceeds that of any other relative fair clique in G. To solve this problem, we first propose a method based on greedy coloring and attribute analysis. We construct optimal tables for all possible subsets to further improve the accuracy. Using these tables, we develop the OPT algorithm and a search algorithm to find the maximum weight relative fair clique in the graph. Extensive experiments on four real-world datasets validate the performance of the proposed algorithm.