Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose that I have a graph and I divided it to subgraphs which can be overlapping. I want to use these subgraphs in network analyses like centrality calculation, community detection etc. instead of using individual nodes.

Do you know any research about this topic?

share|cite|improve this question

You seem to be heading towards to topic of network motifs (or graphlets), which are currently a hot research topic in a range of disciplines (e.g. computational biology). Finding useful patterns is part of "network motif detection" and "frequent subgraph mining". The literature is growing very rapidly in these areas.

Some examples that seem relevant to your question are:

  • Dividing a network into subgraphs has applications in data compression. If a subgraph appears numerous times over, it can be stored in a dictionary are copies are replaced by a dictionary reference. (Papers on this topic can be found by searching for "network motif graph compression" or "frequent subgraph graph compression".)

  • Networks can be compared (e.g. model networks vs. real-world networks) via their "graphlet degree distribution" (e.g. ref.).

share|cite|improve this answer
Good directions, thanks. I suspect my subgraphs are not being simple so I don't expect higher frequencies for different subgraphs. One other point I really care about is how do they interact with other subgraphs such as does a specific subgraph very central to main graph? – metdos Apr 18 '13 at 21:21
Another research about subgraps: – metdos Apr 18 '13 at 21:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.