In social networks analysis one of the major concerns is identification of cohesive subgroups os actores within a network. Friendship relation, publications citation, and many other more. Many studies and researches are focused on social network analysis, including in data mining. It is really important to find patterns in behavior of large online social networks, so the firms behind are able to create better mechanism to handle all that information with lower cost.

Online services such as Orkut, Facebook, Twitter and so on, have millions of users using their services simultaneously and interacting with others. Even in different services, the behavior of the network is similar.

People tend to interact in the same way as they do in real life, in a structure called “small world”, where people in a social network can reach any other person with less than seven steps. Such behavior can be studied to prevent disease propagation or to predict how fast an information can flow in society.

Several notions were introduced to formally describe cohesive groups: cliques, n–cliques, n–clans, n–clubs, k–plexes, k–cores, lambda sets, . . . For most of them it turns out that they are algorithmically difficult, classified as NP hard. However for cores very efficient algorithm exists.

[hide][/hide]