I recently came across this term recurrent heavy subgraph
in a talk. I don't seem to understand what it means and Google doesn't seem to show any good results. Can someone explain what this means in detail.
1 Answer
The term may best be expressed as a Recurrent, Heavy Subgraph. That is, a subgraph which is both Recurrent and Heavy.
Heaviness of a subgraph refers to heavily connected vertices- that is, nodes which are connected many times ("many" being relative to the network in question).
Recurrent refers to the propensity of a subgraph to occur more than once.
Thus, a Recurrent Heavy Subgraph is a densely connected set of vertices which occurs several times in the overall network.
These subgraphs are often used to determine properties of a network.
For example: In a network of emails interactions within a company organized into 4-person teams with one member acting as the lead, each team's email activity (if they email between themselves sufficiently to be considered "heavy") could be described as a Heavy Subgraph. The fact that these subgraphs occur many times in the network make them Recurrent Heavy Subgraphs. If one was searching for structure in the network, noticing that these recurrent, heavy subgraphs exist would go a long way toward determining the organization of the network as a whole.