What would be the best way to determine a weighted clique?

I'm working on implementing a particular kind of market basket analysis in Neo4j, adapted from "Graph-Based Structures for the Market Baskets Analysis"

The paper defines a clique:

"A clique can represent a common interest group. Given a graph representing the communication among a group of individuals in an organization, each vertex represents an individual, while edge (i,j) shows that individual i regularly communicates with individual j."

And goes on to discuss a graph containing weights:

"If a graph with weights in the edges is used, the most weighted clique corresponds to the common-interest group whose elements communicate the most among themselves. This structure allows the representation of sets of elements strongly connected."

I've gotten as far as building a graph with weights:

Now I'm casting about for the best algorithm to run on the weighted-edge graph to find maximally-weighted cliques.

Minimum Weight Spanning Tree and Strongly Connected from @amy.hodler's both look promising. Is there a standard way to do this?

Any of the community detection algorithms would be a good choice here: we have a great developer guide that explains different techniques, or you can get more details & code snippets in our docs. I might start with Speaker Listener Label Propagation (able to detect over lapping communities) or Louvain.

1 Like