Groups, clusters, cliques, and clubs

The world is clumpy and almost everything interesting and important happens at a level between the more easily grasped extremes of small and huge: groups between individuals and society; molecules between atoms and the universe, teams between players and leagues; events and engagements between experience and lifetimes; xxxxx between transactions and markets.

In the social world groups and categories are a fundamental unit of action, social control, identity and how we make sense of the world. But what is a group?

#### Defining and Identifying Groups

One property of network structure is how it can be partitioned into clusters and groups.

A note on terminology: we will use the concept "maximal" to describe the largest entity (here almost always a set of vertices) with a particular property. Sometimes a slightly smaller set will still have the property, but we are interested in adding vertices to the entity until no more can be added without losing the property in question. For example, a brother and sister might have the property that they are related and live together but we might not call them a family if our definition of family was "a maximal set of related individuals living under one roof" because we could add other siblings and parents to the set.

#### Cliques, k-plexes, k-cores, components, clans, and clubs.

Clique "from Luce & Perry (1949), who used complete subgraphs in social networks to model cliques of people"[((bibcite wiki-clique))].

Definition: subset of vertices such that every pair of vertices in the subset is connected by an edge

Relaxing the clique definition

N-clique : allow vertices to be connected by paths longer than 1

but can produce stringy structures and the vertices on the path might not even be in the group. If we add the rule that connectors must be in the group we get an N-clan.

OR, we can relax the "you have to be connected to everybody" rule. If we say "all but one of the group members" we call it a 1-plex. And in general, if node is connected to all by k members of the group it's a k-plex.

A k-core has nodes that are connected to at least k members of the group.

Components in weighted graphs. Suppose edge weight is how many things two nodes have in common. Then we can imagine a sliding threshold in which the graph splits up into components as we raise the "standard" for treating an edge as a connection.

#### Applications

Bibliography
: wiki-clique : Wikipedia Clique (graph theory)
page revision: 1, last edited: 10 Apr 2012 22:46