logo

SCIENCE CHINA Information Sciences, Volume 64 , Issue 5 : 150105(2021) https://doi.org/10.1007/s11432-020-3069-4

Solving diversified top-$k$ weight clique search problem

More info
  • ReceivedMay 18, 2020
  • AcceptedAug 4, 2020
  • PublishedMar 29, 2021

Abstract

There is no abstract available for this article.


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant Nos. 61976050, 61403076, 61806050, 61806082) and Fundamental Research Funds for the Central Universities (Grant No. 2412019FZ050).


Supplement

Appendix A.


References

[1] Zheng X, Liu T, Yang Z. Large cliques in Arabidopsis gene coexpression network and motif discovery. J Plant Physiol, 2011, 168: 611-618 CrossRef Google Scholar

[2] Conrad L, Aaron M, Fergal R, et al. Detecting highly overlapping community structure by greedy clique expansion. In: Proceedings the 4th SNA-KDD Workshop on Social Network Mining and Analysis, Washington, 2010. 112--119. Google Scholar

[3] Krause A, Guestrin C: Near-optimal Observation Selection using Submodular Functions. In: Proceedings AAAI Conference on Artificial Intelligence, Canada, 2007. 22--26. Google Scholar

[4] Berry N M, Ko T H, Moy T, et al. Emergent clique formation in terrorist recruitment. In: Proceedings the AAAI Workshop on Agent Organizations: Theory and Practice, Menlo Park, 2004. Google Scholar

[5] Feige U. J ACM, 1998, 45: 634-652 CrossRef Google Scholar

[6] Yuan L, Qin L, Lin X. Diversified top-k clique search. VLDB J, 2016, 25: 171-196 CrossRef Google Scholar

[7] ChuMin L, Felip Manyà Zhe Q, et al. Exact MinSAT Solving. In: Proceedings the 13th International Conference on Theory and Applications of Satisfiability Testing, Edinburgh, 2010. 363--368. Google Scholar

[8] RC2: an Efficient MaxSAT Solver. SAT, 2019, 11: 53-64 CrossRef Google Scholar

[9] Fahiem B, Matti J, Ruben M. MaxSAT Evaluation 2019: Solver and Benchmark Descriptions. Department of Computer Science Report Series B-2019-2. 2019. Google Scholar

  •   

    Algorithm 1 To-Soft-Clause

    Require:a literal-weighted soft clause $(x_{is},~w(v_i))~\vee~(x_{js},~w(v_j))~\vee\dots~\vee~(x_{rs},~w(v_r))$;

    Output:a set of soft clauses $C$

    $W~\leftarrow~\{w(v_i),~w(v_j),~\dots,~w(v_r)\}$;

    $L~\leftarrow~\{x_{is},~x_{js},\dots,~x_{rs}\}$;

    $\delta~\leftarrow~{\rm~min}~W$;

    while $L~\neq~\emptyset$ do

    Add a soft clause ($c,~\delta$) to C, where $c$ is a disjunction of all literals in $L$;

    Delete the weights equivalent to $\delta$ from $W$ and the literals whose weight is equal to $\delta$ from $L$;

    $W$ is updated by each weight in $W$ minus $\delta$;

    $\delta~\leftarrow~{\rm~min}~W$;

    end while

    return C.