Community Detection in Graphs — a Casual Tour by Jeremy Kun.
From the post:
Graphs are among the most interesting and useful objects in mathematics. Any situation or idea that can be described by objects with connections is a graph, and one of the most prominent examples of a real-world graph that one can come up with is a social network.
Recall, if you aren’t already familiar with this blog’s gentle introduction to graphs, that a graph
is defined by a set of vertices
, and a set of edges
, each of which connects two vertices. For this post the edges will be undirected, meaning connections between vertices are symmetric.
One of the most common topics to talk about for graphs is the notion of a community. But what does one actually mean by that word? It’s easy to give an informal definition: a subset of vertices
such that there are many more edges between vertices in
(the complement of
Thinking that for some purposes, communities of nodes could well be a subject in a topic map. But we would have to be able to find them. And Jeremy says that’s a hard problem.
Looking forward to more posts on communities in graphs from Jeremy.