Single community detection from sample nodes

I am trying to find a community detection algorithm that given one or more nodes that are known to belong to the same community will return a collection of other nodes that are likely from the same community. I am familiar with Louvain and have used it experimentally, but it labels all the communities at once in advance. This problem only requires that one community be identified at a time. Is this even possible because a community can only be defined by its connectivity relative to whole graph?

Edit: I found this article "Searching for a Single Community in a Graph" https://arxiv.org/abs/1806.07944. If you know of anything similar to this, particularly if it has been implemented already in neo4j please let me know.

Is there a reason you can't compute all of the communities ahead of time? The paper you've found appears to be a way of avoiding the identification of all of the communities in order to speed up calculations, but most of our community detection algorithms should be fast enough that you don't need that optimization. If you wanted to pre-identify certain nodes as being in the same community, you could employ seeding as well.

I suppose you could use Node2Vec, tuned for homophily, to calculate your node embeddings, and then use cosine similarity to find the most similar nodes ... but that seems like it would take longer than simply running Louvain and finding all the nodes in the same community as your target node.

1 Like

The specific use-case here is an online process where image features from a video stream are continuously added to the graph. Edges connect features that are likely to be nearby. At each time-step a node along with some edges are added to the graph, and the objective is to try to see what community of features the new feature belongs to. Node2Vec sounds interesting. But perhaps running Louvain each time is possible, especially if it can take the existing community labels and just update the new unlabeled node.