|
I am doing network resilience analysis of a co-occurrence network of words. What I would like to understand is that, what is the minimum fraction of total nodes that must be present in a connected component(sub-graph) of a network for it to be considered as a giant component. For example, in a network of 20,000 nodes if the maximum nodes a sub-graph contains is say 3, can the 3 node sub-graph be considered a giant component? |
|
You may want to plot the size of the giant component as a function of the number of edges removed. Then you can either i) compare such plots or ii) look for areas where the size of the giant component drops quickly with small change in number of edges removed. ii) may help you clarify the notion of "destruction" in your case. Wikipedia defines Giant Component as containing more than majority nodes (>50%). But that seems arbitrary and your threshold would depend on your application. See Jacob's comment. The question is what is the right measure of the utility of the resulting network. 100% giant component that is poorly connected may be worse than well connected giant component of 90%. Thanks, Vaclav. I have re-framed my query to make my doubt more lucid, and updated the post. Anyways, your answer clarifies my doubt.
(Jul 08 '11 at 12:17)
aseembehl
|
|
Look at it as the fraction of nodes that remain in your new giant component at the end of the attack. There is no threshold in general (though in some cases, you want all nodes to remain in the giant component, e.g. in an electrical or telecom network), but you can evaluate resilience by comparing nodes remaining after different types of attacks. |
