摘要
Launching attacks against community detection to significantly deteriorate its performance has received increasing research attention recently due to the importance and wide applications of community detection. However, we observe that most previous attacks suffer from two major weaknesses: i) the negligence of community structures in their proxy metrics, and ii) limited attack scope. To tackle these issues, we propose a new research problem, Perturbing Community Detection with <inline-formula><tex-math notation="LaTeX"> μ </tex-math> <mml:math><mml:mi>μ</mml:mi></mml:math><inline-graphic xlink:href="shen-ieq1-3637867.gif"/> </inline-formula>-Triad Minimization (<inline-formula><tex-math notation="LaTeX"> μ </tex-math> <mml:math><mml:mi>μ</mml:mi></mml:math><inline-graphic xlink:href="shen-ieq2-3637867.gif"/> </inline-formula>-PerCD) , based on a new metric proposed in this paper, named <inline-formula><tex-math notation="LaTeX"> μ </tex-math> <mml:math><mml:mi>μ</mml:mi></mml:math><inline-graphic xlink:href="shen-ieq3-3637867.gif"/> </inline-formula>-triad , to attack community detection more effectively. We first present analysis results to justify the effectiveness of <inline-formula><tex-math notation="LaTeX"> μ </tex-math> <mml:math><mml:mi>μ</mml:mi></mml:math><inline-graphic xlink:href="shen-ieq4-3637867.gif"/> </inline-formula>-triads by comparing it with many other candidate proxy metrics. Also, we illustrate the rationale behind the formulation of <inline-formula><tex-math notation="LaTeX"> μ </tex-math> <mml:math><mml:mi>μ</mml:mi></mml:math><inline-graphic xlink:href="shen-ieq5-3637867.gif"/> </inline-formula>-PerCD problem with experiments on real datasets. Then, we analyze the NP-hardness of <inline-formula><tex-math notation="LaTeX"> μ </tex-math> <mml:math><mml:mi>μ</mml:mi></mml:math><inline-graphic xlink:href="shen-ieq6-3637867.gif"/> </inline-formula>-PerCD and propose two <inline-formula><tex-math notation="LaTeX"> ¼(1-(1/e)) </tex-math> <mml:math><mml:mrow><mml:mfrac><mml:mn>1</mml:mn><mml:mn>4</mml:mn></mml:mfrac><mml:mrow><mml:mo>(</mml:mo><mml:mn>1</mml:mn><mml:mo>-</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mi>e</mml:mi></mml:mfrac><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math><inline-graphic xlink:href="shen-ieq7-3637867.gif"/> </inline-formula>-approximation algorithms, named <inline-formula><tex-math notation="LaTeX"> μ </tex-math> <mml:math><mml:mi>μ</mml:mi></mml:math><inline-graphic xlink:href="shen-ieq8-3637867.gif"/> </inline-formula>-Triad Minimization with Edge Addition (<inline-formula><tex-math notation="LaTeX"> μ </tex-math> <mml:math><mml:mi>μ</mml:mi></mml:math><inline-graphic xlink:href="shen-ieq9-3637867.gif"/> </inline-formula>MEA) and <inline-formula><tex-math notation="LaTeX"> μ </tex-math> <mml:math><mml:mi>μ</mml:mi></mml:math><inline-graphic xlink:href="shen-ieq10-3637867.gif"/> </inline-formula>MEA+ , where <inline-formula><tex-math notation="LaTeX"> μ </tex-math> <mml:math><mml:mi>μ</mml:mi></mml:math><inline-graphic xlink:href="shen-ieq11-3637867.gif"/> </inline-formula>MEA+ is an efficiency-enhanced version of <inline-formula><tex-math notation="LaTeX"> μ </tex-math> <mml:math><mml:mi>μ</mml:mi></mml:math><inline-graphic xlink:href="shen-ieq12-3637867.gif"/> </inline-formula>MEA while retaining the approximation ratio. Extensive experiments on real datasets demonstrate the effectiveness of the proposed algorithm in attacking various community detection algorithms, significantly outperforming the other state-of-the-art baselines.