How fast can you count stars? Not those in the night sky, but stars present in a network. The two types of stars are
rather different, but they share some
properties. They are both interesting to
observe and neither is trivial to count.
Social networks might be the
most ubiquitous example of networks
encountered by an everyday person.
However, networks are useful to
describe and model many other
phenomena. For example, food
chains can be modeled with directed
networks that show relations between
predators and their prey. Networks of
co-authorships might also not come
as a surprise. Further, networks can
be used to simplify representation of
complex relationships in disciplines
such as chemistry, where they
summarize complex chemical
structures. To build a network we need
a set of objects that represent nodes
and some measure of connectedness
between pairs of these objects.
Connected object pairs define edges
in the graph, which is a mathematical
term for a network. Networks are
used to represent binary relations in
a visually appealing manner that is
convenient for further analysis.
Analyzing networks usually involves
detecting groups of tightly connected
nodes known as communities, and
searching for interesting patterns in
the network. These patterns are small
subgraphs, which can be induced
or non-induced, depending on the
application (see Figure 1). There
are several possible scenarios when
looking for patterns. We could search
for frequent patterns in a single
network or for patterns that occur in
sufficiently many networks from a
larger database. We refer to network
patterns that are over-represented
in a given network as motifs. In other
words, motifs are present surprisingly
more often in the observed network
than in an appropriately defined
random network. If we are interested
in frequencies of all possible small
patterns, we usually refer to them
Counting Stars: Pattern
counting in networks
BY TOMAZ HOČEVAR
Figure 1: Induced and non-induced subgraphs.
The figure illustrates an induced (on the left) and a non-induced occurrence (on the right)
of a four-node star in a net work. Induced subgraphs are defined by a subset of nodes and
contain all existing edges bet ween their nodes. On the other hand, non-induced subgraphs
consist of a subset of existing edges bet ween their nodes.
Figure 2: Graphlet orbits.
There exist six connected simple graphs (graphlets) with four nodes. They follow from left to right: path, claw (star), cycle, paw,
diamond, and complete graphlet. The 11 orbits are illustrated with different shades of gray. For example, the central node of a star
belongs to a different orbit than its remaining nodes.