bullet Sensors & Transducers Journal

    (ISSN: 2306-8515, e-ISSN 1726-5479)

   

    About this Journal

   Information for Authors

   Editorial Board

   Editorial Calendar

   Current Issue

   Browse Journal

S&T journal's cover

Submit Press Release

Submit White Paper

25 Top Downloaded Articles (2007-2012)

Search

Contact Us

 

 

 

 

Vol. 234, Issue 6, June 2019, pp. 37-43

 

Bullet

 

Local Community Detection of High Density: an Upper Bound for the Optimal Solution
 

Patricia CONDE CESPEDES

LISITE-ISEP, 10 rue de Vanves, 92130 Issy-les-Moulineaux, Paris
Tel.: (+33) 01 49 54 52 41

E-mail: patricia.conde-cespedes@isep.fr

 

Received: 15 May 2019 /Accepted: 15 June 2019 /Published: 30 June 2019

Digital Sensors and Sensor Sysstems

 

Abstract: Community detection in complex networks has attracted so much attention in the last years. Usually, community detection is referred to the problem of partitioning an entire network. In contrast, local community detection aims to detect the community of a given node in the network. This can be useful when we do not have information concerning the entire network or when there is a specific node of interest in the network. In this paper, we focus on the problem of detection of local communities of very high density. Communities of maximal density are called complete cliques in graph theory. In real complex networks, whose degree distribution follows a power law, usually complete cliques are small sets of nodes. This led to the problem of finding quasi- cliques of maximal size. This problem is NP-hard. Some heuristics on the optimal solution were recently proposed. In this paper, we propose an algorithm to calculate an upper bound on the optimal solution in order to evaluate the existing heuristics. The proposed upper bound will be evaluated experimentally on real networks.

 

Keywords: Local Community detection, a-quasi-clique, Density, Maximal a-quasi-clique problem, Upper bound.

 

Acrobat reader logo Click <here> or title of paper to download the full pages article in pdf format

 

 

This work is licensed under a Creative Commons 4.0 International License

 

 Creative Commons License
 

 

 

 

 


1999 - 2019 Copyright , International Frequency Sensor Association (IFSA) Publishing, S.L. All Rights Reserved.


Home - News - Links - Archives - Tools - Voltage-to-Frequency Converters - Standardization - Patents - Marketplace - Projects - Wish List - e-Shop - Sensor Jobs - Membership - Videos - Publishing - Site Map - Subscribe - Search

 Members Area -Sensors Portal -Training Courses - S&T Digest - For advertisers - Bookstore - Forums - Polls - Submit Press Release - Submit White Paper - Testimonies - Twitter - Facebook - LinkedIn