As per the definition of power law, the fraction P(k) of nodes with k degree for large values of k , given by
P(k) ~k ^-r .
In this definition, the term large value is not clearly defined. Does large implies 100 or 10^3 or 10^6?
Does the definition implies that vertices in power law graphs have almost constant degree with only few exceptions called hub nodes which have very degree may be 100times higher than other vertices?
If the above statement is true, then why do the degree distribution graph for powerlaw graphs do not have only few points with high value of degree and other nodes at the end of disconnected curve compared to close points on decaying curve as in this plot yahoo_web_graph[ (http://bickson.blogspot.in/2011/12/preview-for-graphlab-v2-new-features.html)][1]
Is this definition enough to get the number of hub vertices present in the graph or fraction of edges incident on them, given the number of vertices in the graph?
>Does the definition implies that vertices in power law graphs have almost constant degree with only few exceptions called hub nodes which have very degree may be 100times higher than other vertices?
No, the distribution of degrees is continuous.
The log-log you cited is similar to the representation of a power-law, it shows on a log-log scale a lot a vertices with small degree and very few vertices with very high degree, but between these values, there is a lot of vertices which also respect the power-law degree distribution.
There is no clear definitions of the hub, because the distribution of hub nodes is continuous.
Thanks Philippe Gauron for your response.
Is it possible to get the number of incident edges on the hub with the largest degree given only the number of vertices for a graph having powerlaw distribution?
I am mainly interested in finding average path length for powerlaw graphs. I want to find out for any random vertex selected, within how many hops I can reach a hub and what fraction of the vertices are connected to the hub vertex?
Before answering, I need some precisions :
- What do you mean by hub? How do you define it?
- What do you mean by edge with a largest degree?
- How do you build your powerlaw graph? In particular (but not only), is it connected?
What do you mean by edge with a largest degree?
>> Sorry for the ambiguous wording. I wanted to say hub with the largest degree.
- What do you mean by hub? How do you define it?
>> There is no clear definition for this. But I am mainly interested in vertex with highest degree.
So my question is, given a graph G follows power law and has n vertices, ( G is undirected, unweighted and connected )
1. what is the expected value of the maximum degree for a vertex.
2. what is the expected length of the shortest path from a randomly picked vertex, to the hub(maximum degree vertex).
- How do you build your powerlaw graph? In particular (but not only), is it connected?
>> Thanks for this question. It made me read about power law graph generators. I read about Barabási–Albert model, which requires two input parameters (m0: initial network of nodes and m1 : new node is connected to m ≤ m0 existing nodes) using a preferential attachment.
But I am not clear how to define the input parameters, to get graphs similar to real world graphs like the one cited earlier.
Hi,
I think you are following the right line of understanding. Barabási–Albert model explains how preferential attachment leads to power law and thereby helps us simulating scale-free networks. However, social networks are not just any form of scale-free network. For example, the r you have mentioned in k^-r is usually 3 in Barabási–Albert model, which may not be true for most of the real-world networks. Similarly, for a real-world network, the typical features representing a random network like average path length or clustering co-efficient may not be exactly like as it is defined in the Barabási–Albert model.
https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model
So if you want to simulate a real-world network using Barabási–Albert model, you have to choose the parameters in such a way so that its features matches the real-world network's features (as you want them to be). Tuning the parameters to match multiple features at the same time may be a non-trivial task and may lead to an optimization problem.
Hubs are more than just high degree nodes. It has a recursive definition. You may have a look at the HITS algorithm to understand more about them.
https://en.wikipedia.org/wiki/HITS_algorithm
- Badges
- Science topic
- Similar topics
- Mathematics
- Statistics
- Statistical Analysis
- Data Analysis
- Dataset
- Big Data