Scalable motif-aware graph clustering

Understand

We develop new methods based on graph motifs for graph clustering, allowing more efficient detection of communities within networks.

• We focus on triangles within graphs, but our techniques extend to other clique motifs as well.
• Our intuition, which has been suggested but not formalized similarly in previous works, is that triangles are a better signature of community than edges.
• We therefore generalize the notion of conductance for a graph to {\em triangle conductance}, where the edges are weighted according to the number of triangles containing the edge.