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)


Contact Us





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




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


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