I am interested in any papers on estimating the size of a graph. I'm particularly interested in what assumptions one would have to make to do the estimation (if one can at all under different scenarios for how one is constructing or determining different types of networks or graphs). Thank-you for any pointers or for better phrasing on this question.
The common measure for the size of a graph is the number of its edges.
One possible other more sophisticated measure of interest to you is the complexity of a graph. In the paper in attachment you find criteria that "good" network complexity measures should obey, so this might have some link to your search for what should the assumptions be in estimating the "size". The paper also mentions some network complexity measures, and the simplest we could extract would be something like "cardinality of the vertex set" + "cardinality of the arc set". So it would be number of edges plus number of nodes.
Good estimations.
Thank-you for your quick response. The issue I have is not determining the size of a known graph. It is more the problem of estimating the size of a graph (or a network) when I don't know what the "real" size of the graph is. Your idea of looking at complexity metrics (I am familiar with many but by no means all) is interesting because again complexity on the known parts of a network do not automatically generalize to the unknown parts of a network. So this is also one of the questions that interest me - what assumptions must I make to come up with even a reasonable estimation method?
With knowing that the graph has a certain topology
(e.g. scale free, small world) and being able to
take measurements by picking nodes and determining
their particular edge number, an idea would be
to automatically evolve a random graph with
similar characteristics (e.g. degree distribution).
Then you can judge the size of the network by the
size of the model.
Regards,
Joachim
Following Pimiskern's idea, one assumption might be that the graph has certain "qualitative" features like the topology, that might hold across the graph which might help predict from the known regions how the graph it is like in the unknown ones.
But I would also like to suggest something else (if possible): if you found a way of randomly "signaling" a huge number of your known nodes, as much apart as possible from each other, than you could randomly genarate paths from one initial node through a rule like "in each new node you find take a random edge from it". Then you could check how often the paths coming out of the initial node would ever meet any of the previously signaled nodes.
Since the paths would many times be travelling through the unknown regions, the number of times they would ever "come back" to cross your nodes would be a measure of the graph size, because the number of possible paths increases dramatically with the number of edges of the graph.
Good luck.
so both of these ideas are interesting....I will try them out a little and give you both some feedback on how well they worked. I was thinking of something along the lines of how one can estimate the size of a population by looking for certain repetitions of content.
Thank-you to both responses.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs