Clique Graphs and Overlapping Communities

 

TIM EVANS

IMPERIAL COLLEGE LONDON

 

I define a 'Clique Graph', and show that such hypergraphs are a natural extension of the line graph. I then describe how to construct a weighted clique graph which is a more useful way to capture structure of a general graph. This extends earlier work on weighted line graphs (Evans and Lambiotte, 2009). I illustrate the problem of community detection to the use of weighted clique graphs. In doing so we show that the clique percolation method (Palla et al, 2005) is a particular special case of the use of clique graphs. The Karate Club example (Zachary, 1977) provides one example where clique percolation fails yet a general weighted clique graph approach provides a simple yet effective way of determining community structure. Other examples will also be considered.