For a given undirected graph with N nodes and its adjacency matrix, suppose that there is at least one set of n nodes in which every member node is a one-hop neighbor of the others in the set. (n << N)
In this situation, what is an algorithm to find such a set of nodes?
For example, this is a sample adjacency matrix (link: GitHub Gist) with 42 nodes. And it is known that there is a set in which 3 nodes are one-hop neighbors of each other. Then, what is the composition of the set?
My final goal is to do this procedure with about 450 nodes to find a set containing 9 one-hop neighbor nodes. Thus, I am looking for a solution that is scalable and efficient.
A set of nodes in a graph that are neighbours of each other is called a clique, and finding the largest clique in a graph, or indeed whether any clique of a specified size even exists in the graph, is a classic NP-hard problem.
Some NP-hard problems, called fixed-parameter tractable (FPT) problems, can be solved efficiently even for large n, provided that some problem parameter (besides the size) is small: here the obvious parameter is the size of the largest clique. Unfortunately Maximum Clique is not FPT with respect to this parameter, and the best known algorithms are exponential in n. Several are mentioned on the Wikipedia page. Of course, since you already know a clique of the given size exists, you might get lucky and find it quickly with a heuristic.
Note the difference between maximum (largest possible) and maximal (can't be grown) cliques.