Maximal Clique Search in Weighted Graphs

Searching for <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq1-3239409.gif"/></alternatives></inline-formula>-cliques in graphs has been an important problem in graph analysis due to its large number of applications. Previously, finding <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq2-3239409.gif"/></alternatives></inline-formula>-cliques in weighted graphs aimed at finding cliques with the largest sum of weight (with no distinction between the edge or the vertex weights), usually called the sum model. However, the algorithms under the sum model may result in solutions consisting of low-weight vertices or edges (outliers). To address this issue, we propose a new model named maximal <inline-formula><tex-math notation="LaTeX">$(S, C, K)$</tex-math><alternatives><mml:math><mml:mrow><mml:mo>(</mml:mo><mml:mi>S</mml:mi><mml:mo>,</mml:mo><mml:mi>C</mml:mi><mml:mo>,</mml:mo><mml:mi>K</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="yu-ieq3-3239409.gif"/></alternatives></inline-formula>-clique in weighted graphs and study the problem of maximal (<inline-formula><tex-math notation="LaTeX">$S, C, K$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>S</mml:mi><mml:mo>,</mml:mo><mml:mi>C</mml:mi><mml:mo>,</mml:mo><mml:mi>K</mml:mi></mml:mrow></mml:math><inline-graphic xlink:href="yu-ieq4-3239409.gif"/></alternatives></inline-formula>)-clique search (MCS). We first propose an enumeration-based algorithm MCSE, which checks every <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq5-3239409.gif"/></alternatives></inline-formula>-clique to identify the maximal (<inline-formula><tex-math notation="LaTeX">$S, C, K$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>S</mml:mi><mml:mo>,</mml:mo><mml:mi>C</mml:mi><mml:mo>,</mml:mo><mml:mi>K</mml:mi></mml:mrow></mml:math><inline-graphic xlink:href="yu-ieq6-3239409.gif"/></alternatives></inline-formula>)-clique. To improve the efficiency, we further propose two improved algorithms MCSP and MCSC. Instead of checking every possible <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq7-3239409.gif"/></alternatives></inline-formula>-clique, MCSP focuses on (<inline-formula><tex-math notation="LaTeX">$S, C$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>S</mml:mi><mml:mo>,</mml:mo><mml:mi>C</mml:mi></mml:mrow></mml:math><inline-graphic xlink:href="yu-ieq8-3239409.gif"/></alternatives></inline-formula>) values that cannot be dominated and obtains the maximal <inline-formula><tex-math notation="LaTeX">$(S, C, K)$</tex-math><alternatives><mml:math><mml:mrow><mml:mo>(</mml:mo><mml:mi>S</mml:mi><mml:mo>,</mml:mo><mml:mi>C</mml:mi><mml:mo>,</mml:mo><mml:mi>K</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="yu-ieq9-3239409.gif"/></alternatives></inline-formula>-cliques directly based on these values. MCSC is devised by further optimizing MCSP based on some key observations on maximal cliques and cliques’ nesting property. We also propose two index structures, BCS-Index and ICS-Index, to achieve optimal query. The former stores all maximal <inline-formula><tex-math notation="LaTeX">$(S, C, K)$</tex-math><alternatives><mml:math><mml:mrow><mml:mo>(</mml:mo><mml:mi>S</mml:mi><mml:mo>,</mml:mo><mml:mi>C</mml:mi><mml:mo>,</mml:mo><mml:mi>K</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="yu-ieq10-3239409.gif"/></alternatives></inline-formula>-cliques, while the latter uses the clique's nesting property to reduce the space cost of index construction. Extensive experiments conducted on six real graphs demonstrate the efficiency and effectiveness of our proposed algorithms.