Finding dense subgraphs with maximum weighted triangle density

DOI10.1016/J.INS.2020.06.004MaRDI QIDQ2666852zbMATH OpenOpenAlexFDO

Authors Jiabing Wang, Rongjie Wang, Jia Wei, Qianli Ma, Gui-Hua Wen

Publication date 23 November 2021

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ins.2020.06.004

zbMATH Keywords

dense subgraphgraph algorithmsgraph miningminimum cutnear-clique extraction

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Finding densest \(k\)-connected subgraphs
• On Finding Dense Subgraphs
• Finding Dense Subgraphs with Size Bounds
• Discounted average degree density metric and new algorithms for the densest subgraph problem
• Top-\(k\) overlapping densest subgraphs

Cites work

• A Fast Parametric Maximum Flow Algorithm and Applications
• A Faster Deterministic Maximum Flow Algorithm
• Algorithms for node-weighted Steiner tree and maximum-weight connected subgraph
• Complexity of finding dense subgraphs
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• Finding Dense Subgraphs with Size Bounds
• Finding lasting dense subgraphs
• Greedily Finding a Dense Subgraph
• scientific article; zbMATH DE number 1670532 (Why is no real title available?)
• Main-memory triangle computations for very large (sparse (power-law)) graphs
• Max flows in O(nm) time, or better
• Near optimal solutions for maximum quasi-bicliques
• On Finding Dense Subgraphs
• On size-constrained minimum \(s\mathrm{-}t\) cut problems and size-constrained dense subgraph problems
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
• The dense \(k\)-subgraph problem
• The structure of scientific collaboration networks
• Top-\(k\) overlapping densest subgraphs

Cited in

(7)

• Top-\(k\) overlapping densest subgraphs
• Finding density-based subspace clusters in graphs with feature vectors
• Finding densest \(k\)-connected subgraphs
• Dense subgraphs in biological networks
• Efficient mining algorithm of K-densely probability attribute sub-graph in a complicated network
• In search of dense subgraphs: How good is greedy peeling?
• OCSM: finding overlapping cohesive subgraphs with minimum degree

Describes a project that uses

Uses Software

• MotifCut
• SNAP

This page was built for publication: Finding dense subgraphs with maximum weighted triangle density

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2666852)