Finding Overlapping Clusters in a Highly Connected Graph from a Given Difference Density
Conference proceedings article
Authors/Editors
No matching items found.
Strategic Research Themes
Publication Details
Author list: Lavangnananda, Kittichai; Hemmatqachmas, Muhammad Aslam
Publisher: Hindawi
Publication year: 2020
Start page: 4620
End page: 4626
Number of pages: 7
ISBN: 9781730000000
ISSN: 0146-9428
eISSN: 1745-4557
Languages: English-Great Britain (EN-GB)
View in Web of Science | View on publisher site | View citing articles in Web of Science
Abstract
In many fields, there may exist relationship among data or information used. Social network is a good example where relationship among members can be high and complex. Their interaction can be represented as a graph. Dividing such examples into smaller groups with similar characteristics can be translated into Graph Clustering. It is sub-field of clustering with numerous applications ranging from analysis of social network to computer network to bioinformatics. This work is an attempt to implement a novel overlapping clustering of a highly connected undirected unweighted graph. The main objective is to determine overlapped clusters in such a graph under a constrain of a specified different density. The approach starts with finding a spanning tree of the graph in order to discover all minimum cliques within the graph. These cliques are utilized by considering a clique with and an average sum of degrees of all three nodes. Such average cliques are the basis for expansion of clusters. Any clique or node that may already be a member of a cluster is allowed to be re-considered in the formation of other clusters. Hence, this enables overlapped clusters to appear. The process is carried out iteratively until all cliques and edges are considered. The two popular quality graph metrics, conductance and coverage, are selected to evaluate the overlapping clustering. Two examples of highly connected graphs are chosen for demonstration. The proposed approach is able to discover overlapping clusters from a given specific difference density. Result from this work can be used as a starting point analysis of highly connect graph, especially in the recent popularity of social network analysis. © 2020 IEEE.
Keywords
Clique, Difference Density, Graph Clustering, Overlapping Clustering, social network, Spanning Tree
Contact Information