NDLI: Finding large $$k$$ -clubs in undirected graphs

Content Provider	Springer Nature Link
Author	Hung, Ling Ju Lin, Chih Ren Chang, Maw Shang Su, Ping Chen
Copyright Year	2012
Abstract	Finding cohesive subgroups is an important issue in studying social networks. Many models exist for defining cohesive subgraphs in social networks, such as clique, $$k$$ -clique, and $$k$$ -clan. The concept of $$k$$ -club is one of them. A $$k$$ -club of a graph is a maximal subset of the vertex set which induces a subgraph of diameter $$k$$ . It is a relaxation of a clique, which induces a subgraph of diameter $$1$$ . We conducted algorithmic studies on finding a $$k$$ -club of size as large as possible. In this paper, we show that one can find a $$k$$ -club of maximum size in $$O^{*}(1.62^n)$$ time where $$n$$ is the number of vertices of the input graph. We implemented a combinatorial branch-and-bound algorithm that finds a $$k$$ -club of maximum size and a new heuristic algorithm called IDROP given in this paper. To speed up the programs, we introduce a dynamic data structure called $$k$$ -DN which, under deletion of vertices from a graph, maintains for a given vertex $$v$$ the set of vertices at distances at most $$k$$ . From the experimental results that we obtained, we concluded that a $$k$$ -club of maximum size can be easily found in sparse graphs and dense graphs. Our heuristic algorithm finds, within reasonable time, $$k$$ -clubs of maximum size in most of experimental instances. The gap between the size of a $$k$$ -club of maximum size and a $$k$$ -club found by IDROP is a constant for the number of vertices that we are able to test.
Ending Page	758
Page Count	20
Starting Page	739
File Format	PDF
ISSN	0010485X
e-ISSN	14365057
Journal	Computing
Issue Number	9
Volume Number	95
Language	English
Publisher	Springer Vienna
Publisher Date	2012-12-23
Publisher Place	Vienna
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Branch and bound Software Engineering Computer Application in Administrative Data Processing Computer Science Artificial Intelligence (incl. Robotics) $$k$$ -Club Network models, deterministic Information Systems Applications (incl. Internet) Graph algorithms $$k$$ -Neighborhood Graph theory (including graph drawing) Computer Communication Networks
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Computational Mathematics Numerical Analysis Computer Science Applications Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Distributed discovery of frequent subgraphs of a network using MapReduce

Internet visualization

Visual discovery of the correlation between BGP routing and round-trip delay active measurements

Some Indices of Alphabet Overlap Graph

Minimal Expansions in Redundant Number Systems and Shortest Paths in Graphs

Sustainable mobile computing

From Methods to Images

Efficent and highly portable deterministic multithreading (DetLock)

Empirical investigation of BitTorrent community graphs

Finding large $$k$$ -clubs in undirected graphs

Similar Documents

Distributed discovery of frequent subgraphs of a network using MapReduce

Internet visualization

Visual discovery of the correlation between BGP routing and round-trip delay active measurements

Some Indices of Alphabet Overlap Graph

Minimal Expansions in Redundant Number Systems and Shortest Paths in Graphs

Sustainable mobile computing

From Methods to Images

Efficent and highly portable deterministic multithreading (DetLock)

Empirical investigation of BitTorrent community graphs

Finding large $$k$$ -clubs in undirected graphs