Discovering Interesting Cycles in Directed Graphs

Florian Adriaens, Cigdem Aslay, Tijl De Bie, Aristides Gionis, Jefrey Lijffijt

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

Abstrakti

Cycles in graphs often signify interesting processes. For example, cyclic trading patterns can indicate inefficiencies or economic dependencies in trade networks, cycles in food webs can identify fragile dependencies in ecosystems, and cycles in financial transaction networks can be an indication of money laundering. Identifying such interesting cycles, which can also be constrained to contain a given set of query nodes, although not extensively studied, is thus a problem of considerable importance. In this paper, we introduce the problem of discovering interesting cycles in graphs. We first address the problem of quantifying the extent to which a given cycle is interesting for a particular analyst. We then show that finding cycles according to this interestingness measure is related to the longest cycle and maximum mean-weight cycle problems (in the unconstrained setting) and to the maximum Steiner cycle and maximum mean Steiner cycle problems (in the constrained setting). A complexity analysis shows that finding interesting cycles is NP-hard, and is NP-hard to approximate within a constant factor in the unconstrained setting, and within a factor polynomial in the input size for the constrained setting. The latter inapproximability result implies a similar result for the maximum Steiner cycle and maximum mean Steiner cycle problems. Motivated by these hardness results, we propose a number of efficient heuristic algorithms. We verify the effectiveness of the proposed methods and demonstrate their practical utility on two real-world use cases: a food web and an international trade-network dataset.
AlkuperäiskieliEnglanti
OtsikkoCIKM 2019 - Proceedings of the 28th ACM International Conference on Information and Knowledge Management
KustantajaACM
Sivut1191-1200
Sivumäärä10
ISBN (elektroninen)9781450369763
DOI - pysyväislinkit
TilaJulkaistu - 3 marraskuuta 2019
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaACM International Conference on Information and Knowledge Management - Beijing, Kiina
Kesto: 3 marraskuuta 20197 marraskuuta 2019
Konferenssinumero: 28

Conference

ConferenceACM International Conference on Information and Knowledge Management
LyhennettäCIKM
MaaKiina
KaupunkiBeijing
Ajanjakso03/11/201907/11/2019

Sormenjälki Sukella tutkimusaiheisiin 'Discovering Interesting Cycles in Directed Graphs'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

  • Siteeraa tätä

    Adriaens, F., Aslay, C., De Bie, T., Gionis, A., & Lijffijt, J. (2019). Discovering Interesting Cycles in Directed Graphs. teoksessa CIKM 2019 - Proceedings of the 28th ACM International Conference on Information and Knowledge Management (Sivut 1191-1200). ACM. https://doi.org/10.1145/3357384.3357970