Christodoulou, Filippos, Nikoletseas, Sotiris, Raptopoulos, Christoforos and Spirakis, Paul G 
ORCID: 0000-0001-5396-3749
(2023)
A Spectral Algorithm for Finding Maximum Cliques in Dense Random Intersection Graphs.
.
|
Text
SOFSEM___Cliques_in_RIGs.pdf - Author Accepted Manuscript Download (1MB) | Preview |
Abstract
In a random intersection graph Gn,m,p, each of n vertices selects a random subset of a set of m labels by including each label independently with probability p and edges are drawn between vertices that have at least one label in common. Among other applications, such graphs have been used to model social networks, in which individuals correspond to vertices and various features (e.g. ideas, interests) correspond to labels; individuals sharing at least one common feature are connected and this is abstracted by edges in random intersection graphs. In this paper, we consider the problem of finding maximum cliques when the input graph is Gn,m,p. Current algorithms for this problem are successful with high probability only for relatively sparse instances, leaving the dense case mostly unexplored. We present a spectral algorithm for finding large cliques that processes vertices according to respective values in the second largest eigenvector of the adjacency matrix of induced subgraphs of the input graph corresponding to common neighbors of small cliques. Leveraging on the Single Label Clique Theorem from [16], we were able to construct random instances, without the need to externally plant a large clique in the input graph. In particular, we used label choices to determine the maximum clique and then concealed label information by just giving the adjacency matrix of Gn,m,p as input to the algorithm. Our experimental evaluation showed that our spectral algorithm clearly outperforms existing polynomial time algorithms, both with respect to the failure probability and the approximation guarantee metrics, especially in the dense regime, thus suggesting that spectral properties of random intersection graphs may be also used to construct efficient algorithms for other NP-hard graph theoretical problems as well.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Uncontrolled Keywords: | Random intersection graphs, Maximum cliques, Heuristics |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 21 Feb 2023 15:47 |
| Last Modified: | 01 Jan 2024 02:31 |
| DOI: | 10.1007/978-3-031-23101-8_2 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3168507 |
Dimensions
Dimensions
