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

A graph $G(V,E)$ is growing with following rule:

At every time step $t$, $An_t$ nodes are added to the graph. When choosing the node to which the new node connects to, we assume that the probability $P$ that a new node will be connected to some node $i$ depends on the degree $k_i$ of node $i$ , such that $P \propto \frac{k_i}{\sum_j k_j}$.

What is the rate of change of the degree $k_i$ of the node $i$?

share|cite|improve this question
Not a full answer, but some thoughts: The sum of the degrees of all the nodes is just twice the number of edges in the graph, as each end of an edge is counted. The increase in the number of edges is just the number of new nodes. If $n_0$ is the number of nodes at time 0, the number of nodes at time $t, n_t=(1+A)^tn_0$. If $e_t$ is the number of edges at time $t, e_t=e_0+((1+A)^t-1)n_0$ – Ross Millikan Apr 14 '12 at 16:49
i think it is $e_t=e_0+(1+A)^{t-1}$...Furthermore adding my thought ....$dk_i/dt=A(A+1)^{t-1}k_i/ \sum_j k_j$ it correct? – user997704 Apr 14 '12 at 16:54
No, the edge count increases proportional to the current number of nodes, not edges, at least if my reading of $An_t$ is correct. But then converting to a differential equation is a good idea. – Ross Millikan Apr 14 '12 at 17:00
I got $dk_i/dt$ as follows $dk_i/dt=(1+A)^t-(1+A)^{t-1}.k_i/ \sum_j k_j$ where $\sum_j k_j=2(1+A)^te_0$..At every time step we are adding $An_t$ nodes to graph and each node is linking to exactly one node so at each time step we are adding $An_t$ edges which is equal to number of nodes added. – user997704 Apr 14 '12 at 17:13
I don't think this is right. If you change the starting graph by doubling every edge, you have twice the edges but the same number of nodes. Your formula $\sum_j k_j=2(1+A)^te_0$ would have twice as many nodes at each generation, but the increase is proportional to the number of nodes. – Ross Millikan Apr 14 '12 at 22:08

Your Answer


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

Browse other questions tagged or ask your own question.