Finding Overlapping Clusters in a Highly Connected Graph from a Given Difference Density

Conference proceedings article

ผู้เขียน/บรรณาธิการ

ไม่พบข้อมูลที่เกี่ยวข้อง

กลุ่มสาขาการวิจัยเชิงกลยุทธ์

รายละเอียดสำหรับงานพิมพ์

รายชื่อผู้แต่ง: Lavangnananda, Kittichai; Hemmatqachmas, Muhammad Aslam

ผู้เผยแพร่: Hindawi

ปีที่เผยแพร่ (ค.ศ.): 2020

หน้าแรก: 4620

หน้าสุดท้าย: 4626

จำนวนหน้า: 7

ISBN: 9781730000000

นอก: 0146-9428

eISSN: 1745-4557

URL: https://www.scopus.com/inward/record.uri?eid=2-s2.0-85103852795&doi=10.1109%2fBigData50022.2020.9378329&partnerID=40&md5=9ae5f7f0f9c3b8eb0580099af4606704

ภาษา: English-Great Britain (EN-GB)

ดูในเว็บของวิทยาศาสตร์ | ดูบนเว็บไซต์ของสำนักพิมพ์ | บทความในเว็บของวิทยาศาสตร์

บทคัดย่อ

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.

คำสำคัญ

Clique, Difference Density, Graph Clustering, Overlapping Clustering, social network, Spanning Tree