# Probability of a path between two vertices, in a modified version of a random graph

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!

• 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). – Anonymous Jun 2 '18 at 14:06
• @Anonymous done. Does it look better? – Daniel Jun 5 '18 at 20:53
• 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.) – joriki Jun 5 '18 at 21:12
• The problem seems rather intractable to me. Do you have any reason to expect that there should be a solution in closed form? – joriki Jun 5 '18 at 21:16
• Sorry for the confusion. Does it look better now? – Daniel Jun 6 '18 at 3:49