A mixed integer linear programming approach for soft graph clustering

Mak-Hau, Vicky and Yearwood, John 2020, A mixed integer linear programming approach for soft graph clustering, in ICDM2020 : Proceedings of IEEE's International Conference on Data Mining, Institute of Electrical and Electronics Engineers (IEEE), Piscataway, N.J., pp. 1166-1171, doi: 10.1109/ICDM50108.2020.00143.

Attached Files
Name Description MIMEType Size Downloads

Title A mixed integer linear programming approach for soft graph clustering
Author(s) Mak-Hau, VickyORCID iD for Mak-Hau, Vicky orcid.org/0000-0002-9306-5780
Yearwood, JohnORCID iD for Yearwood, John orcid.org/0000-0002-7562-6767
Conference name ICDM2020 . Data Mining. IEEE International Conference (2020 : Sorrento, Italy)
Conference location Online : Sorrento, Italy
Conference dates 17 - 20 Nov. 2020
Title of proceedings ICDM2020 : Proceedings of IEEE's International Conference on Data Mining
Editor(s) Cuzzocrea, Alfredo
Zaniolo, Carlo
Publication date 2020
Start page 1166
End page 1171
Total pages 6
Publisher Institute of Electrical and Electronics Engineers (IEEE)
Place of publication Piscataway, N.J.
Keyword(s) integer programming
fuzzy clustering
graph clustering
CORE2020 A*
Summary This paper proposes a Mixed-Integer Linear Pro-gramming (MILP) formulation for Soft Graph Clustering that can be applied to both weighted and unweighted graphs and is polynomial in size. It can provide proven optimal solutions or solutions with proven optimality gap. The solutions will partition the set of vertices in a graph into K (possibly over-lapping) clusters, for K predetermined. The MILP approach can also simultaneously allocate membership proportion for vertices that lie in multiple clusters, and handle restrictions such as cardinality constraints on the size of the overlaps and equal balance of cluster memberships. Our approach requires neither a threshold on edge weights to be predetermined nor the finding of clique neighbourhoods of any size. It does not require the maximum number of clusters to be predetermined. We compare our approach numerically with four existing algorithms: one that requires the finding of clique neighbourhoods, one that performs well on weighted graphs only, one that requires the maximum number of clusters be predetermined, and one that is statistical analysis-based; and discuss in what way our approach outperform these methods.
ISBN 9781728183169
ISSN 1550-4786
Language eng
DOI 10.1109/ICDM50108.2020.00143
Indigenous content off
Field of Research 010206 Operations Research
HERDC Research category E1 Full written paper - refereed
Copyright notice ©2020, IEEE
Persistent URL http://hdl.handle.net/10536/DRO/DU:30148645

Connect to link resolver
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in TR Web of Science
Scopus Citation Count Cited 0 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 75 Abstract Views, 2 File Downloads  -  Detailed Statistics
Created: Mon, 08 Mar 2021, 12:28:26 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact drosupport@deakin.edu.au.