Algorithms For Dummies

  Discovering Graph Secrets 

     201

 output,  you  can  see  that  some  nodes  have  just  one  connection,  some  two,  and 

some more than two. The edges form triads, as previously mentioned. However, 

the most important consideration is that Figure 10-1 clearly shows the clustering 

that occurs in a social network.

Discovering communities

A group of tightly associated people often defines a community. In fact, the term 

clique applies to a group whose membership to the group is exclusive and everyone 

knows everyone else quite well. Most people have childhood memories of a tight 

group of friends at school or in the neighborhood who always spent their time 

together. That’s a clique.

You can find cliques in undirected graphs. Directed graphs distinguish strongly 

between connected components when a direct connection exists between all the 

node pairs in the component itself. A city is an example of a strongly connected 

component  because  you  can  reach  any  destination  from  any  starting  point  by 

 following one-way and two-way streets.

Mathematically, a clique is even more rigorous because it implies a subgraph (a 

part of a network graph that you can separate from other parts as a complete ele-

ment in its own right) that has maximum connectivity. In looking at various kinds 

of social networks, picking out the clusters is easy, but what can prove difficult is 

finding the cliques — the groups with maximum connectivity — within the clus-

ters. By knowing where cliques exist, you can begin to understand the cohesive 

nature of a community better. In addition, the exclusive nature of cliques tends to 

create a group that has its own rules outside of those that might exist in the social 

network  as  a  whole.  The  following  example  shows  how  to  extract  cliques  and 

communities from the karate club graph used in the previous section:

graph = nx.karate_club_graph()

# Finding and printing all cliques of four

cliques = nx.find_cliques(graph)

print ('All cliques of four: %s'

       % [c for c in cliques if len(c)>=4])

# Joining cliques of four into communities

communities = nx.k_clique_communities(graph, k=4)

communities_list = [list(c) for c in communities]

nodes_list = [node for community in communities_list for

              node in community]

print ('Found these communities: %s' % communities_list)

---

202