As discussed in my previous post study in community detection in network , I'm looking for a definition/algorithm that address communities from a network that has several properties as below:
1. high intrinsic clustering
2. communities can overlap on nodes (like your family community and friend community can overlap on you)
3. It's ok for some node to be single island
here is a paper described just like what I wanted:
uncovering the overlapping community structure of complex networks in nature and society
And I found it from cfinder.org
As in the paper:
"we define a community, or more precisely, a k-clique-community as a union of all k-cliques (complete sub-graphs of size k) that can be reached from each other through a series of adjacent k-cliques (where adjacency means sharing k-1 nodes) "
For each node in a community, it's at least a member of a k-clique, which leads to intrinsic clustering.
As a node can belong to different cliques and those cliques can share less then k-1 nodes which mean they belong to different community. This leads to overlap between communities
Finally, there must be some nodes that don't belong to any clique then they form islands.
It's tricky to decide k. if k is too high, there must be too much islands.
If k is 2, then all connected nodes form a community which block the overlap property.
so maybe 3 or 4 would be good choice.
No comments:
Post a Comment