Define $G$ to be random graph, with the following constructiion: The network begins with an initial node. New nodes are added to the network one at a time. Each new node is connected to the existing nodes with a probability that is proportional to the number of links that the existing nodes already have. Formally, the probability ${p_{i}} $ that the new node is connected to node $i$ is $p_{i}={\frac {k_{i}}{\sum _{j}k_{j}}}$, where $ k_{i}$ is the degree of node $i$ and the sum is made over all pre-existing nodes $j$ (i.e. the denominator results in twice the current number of edges in the network). Let's say this graph has $n$ nodes.

Modification of Random Graph: Given the graph $G$, we modify it by adding extra edges to it. For each node pair $i, j$ that are not connected, with probability $q$, we put an edge between them. Call the modified graph $G'$.

Question: what is the probability that there is a path between vertices $i$ and $j$ in G', assuming that there is no path between $i$ and $j$ in G.

Note: not proud of the current title. If you have better suggestions, let me know!

  • 1
    $\begingroup$ I think you may want to clarify the construction. In particular, you may want to make explicit the number - let's call it $n$ - of new nodes added to the initial $m_0$; and how q may, or may not, depend on $n$ (in the latter case, obviously, the probability of having a path between every pair of nodes rapidly converges to 1 as n grows to infinity unless q=0). $\endgroup$ – Anonymous Jun 2 '18 at 14:06
  • $\begingroup$ @Anonymous done. Does it look better? $\endgroup$ – Daniel Jun 5 '18 at 20:53
  • $\begingroup$ The first sentence is confusing. You say that $G$ is defined with either of the following constructions, which I would expect to imply that the following two constructions are equivalent, but then you actually go on to define a graph $G$ in the first construction and an apparently different graph $G'$ in the second construction. You should either change the first sentence or clarify in what sense the two constructions define the same graph $G$. (Also, you announce "Questions:" in the plural, but only one question seems to follow.) $\endgroup$ – joriki Jun 5 '18 at 21:12
  • $\begingroup$ The problem seems rather intractable to me. Do you have any reason to expect that there should be a solution in closed form? $\endgroup$ – joriki Jun 5 '18 at 21:16
  • $\begingroup$ Sorry for the confusion. Does it look better now? $\endgroup$ – Daniel Jun 6 '18 at 3:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.