Modeling directed scale-free object relationships

• US 20050021316A1
• Filed: 04/23/2003
• Published: 01/27/2005
• Est. Priority Date: 04/23/2003
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Riordan, Oliver M., Borgs, Christian H., Chayes, Jennifer T., Bollobas, Bela
• Application Number:
  US10/421,385
• Publication Number:
  US 20050021316A1
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 18/29 Graphical models, e.g. Bayesian networks

Abstract

Systems and methods for generating models of directed scale-free object relationships are described. In one aspect, a sequence of random numbers is generated. Individual ones of these random numbers are then selected over time to generate the directed scale-free object relationships as a graph based on sequences of in-degrees and out-degrees.

Claims

1. A computer-readable medium comprising computer-program instructions executable by a processor for modeling directed scale-free object relationships, the computer-program instructions comprising instructions for:

generating a sequence of random numbers; and

successively selecting individual ones of the random numbers over time to generate models of directed scale-free object relationships in a graph, with graph development depending on both in-degrees and out-degrees.

2. A computer-readable medium as recited in claim 1, wherein the graph is a web graph comprising nodes and directed edges between respective ones of the nodes, the nodes corresponding to web pages and the directed edges corresponding to hyperlinks from one web page to another web page.

3. A computer-readable medium as recited in claim 1, wherein the computer-program instructions further comprise instructions for successively using the random numbers to update the graph by:

(A) adding an edge between a new object and an old object;

(B) adding an edge between two old objects;

or

(C) adding an edge from an old object to a new object according to configurable parameters α

, β and

γ

.

4. A computer-readable medium as recited in claim 1, wherein the computer-program instructions further comprise instructions for adding new edges to the graph as a function of directed preferential attachment.

5. A computer-readable medium as recited in claim 1, wherein the computer-program instructions further comprise instructions for generating the graph as a function of in-degree and/or out-degree shifts δ

_in, and/or δ

_out.

6. A computer-readable medium as recited in claim 1, wherein the computer-program instructions further comprise instructions for modeling the graph as a function of a measured environmental characteristic based on a set of configurable parameters α

, β

, δ

_in and δ

_out.

7. A computer-readable medium as recited in claim 1, wherein an in-degree power law associated with an object represented by the graph is different from an out-degree power law associated with the object.

8. A computer-readable medium as recited in claim 1, wherein an in-degree power law associated with an object represented by the graph is different from an out-degree power law associated with the object such that for a generator with parameters α

, β

, γ

, δ

_out, a proportion of vertices with in-degree equal to di, asymptotically scales as follows;

9. A computer-readable medium as recited in claim 3, wherein the computer-program instructions further comprise instructions based on (A) for updating the graph by adding an edge from a new object v to a random old object w chosen according to a probability distribution with

Pr(w=w_j)∝

(d_in(w_in)+δ

_in).

10. A computer-readable medium as recited in claim 3, wherein the computer-program instructions further comprise instructions based on (B), updating the graph by adding an edge from a first existing object v of the graph to a second existing object w, and wherein objects v and w are chosen according to a probability distribution with

Pr(v=v_i,w=w_j)∝

(d_out(v_i)+δ

_out)(d_in(w_j)+δ

_in).

11. A computer-readable medium as recited in claim 3, wherein the computer-program instructions further comprise instructions based on (C) for updating the graph by adding an edge from a randomly chosen old object w to a new object v, where w is chosen according to a probability distribution with

Pr(w=w_i)∝

d_out(w_i)+δ

_out.

12. A computer-readable medium as recited in claim 3, wherein (A) the computer program instructions further comprise instructions for adding an edge E(i,j) from a new object v_i to an old object w_j by:

dividing interval [0, t+nδ

_in] into n slots of width d_in(w_j)+δ

_in;

selecting a random number r_in uniformly from the interval [0, t+nδ

_in]; and

selecting the old object w_j if the random number r_in falls into a j^th slot.

13. A computer-readable medium as recited in claim 3, wherein the computer-program instructions based on (B) further comprise instructions for adding an edge E(i,j) from an old object v_i to an old object w_j by:

dividing interval [0, t+nδ

_out] into n slots of width d_out(v_i)+δ

_out;

selecting a random number r_out uniformly from the interval [0, t+nδ

_out];

selecting the old object v_i if the random number r_out falls into an i^th slot;

dividing interval [0, t+nδ

_in] into n slots of width d_in (w_j)+δ

_in;

selecting a random number r_in uniformly from the interval [0, t+nδ

_in]; and

selecting the old object w_j if the random number r_in falls into a j^th slot.

14. A computer-readable medium as recited in claim 3, wherein the computer program instructions based on (C) further comprise instructions for adding an edge E(i,j) from an old object w_i to a new object v_j by:

dividing interval [0, t+nδ

_out] into n slots of width d_out(w_i)+δ

_out;

selecting a random number r_out uniformly from the interval [0, t+nδ

_out]; and

selecting the old object w_i if the random number r_out falls into an i^th slot.

15. A computer-readable medium as recited in claim 1, wherein the computer-program instructions further comprise instructions for:

independently generating two random numbers λ

(v) and μ

(v) from specified distributions D_in and D_out for a new vertex v of the graph; and

utilizing the random numbers to update vertices of the graph as follows;

(A) choosing an existing vertex w according to λ

(w)(d_in+δ

_in) such that Pr(w=w_j)∝

λ

/(w_j)(d_in(w_j)+δ

_in);

(B) choosing an existing vertex v according to μ

(v)(d_out+δ

_out) and a second existing vertex w according to λ

(w)(d_in+δ

_in) so that Pr(v=v_i, w=w_j)∝

μ

(v_i)λ

(w_j)(d_out(v_i)+δ

_out)(d_in(w_j)+δ

_in);

or

(C) selecting an existing vertex w according to μ

(w)(d_out+δ

_out) such that Pr(w=w_i)∝

μ

(w_i)(d_out(w_i)+δ

_out).

16. A method to generate models of directed scale-free object relationships, the method comprising:

generating a sequence of random numbers; and

successively selecting individual ones of the random numbers over time to generate models of directed scale-free object relationships in a graph, with the development of the graph depending on both in-degrees and out-degrees.

17. A method as recited in claim 16, wherein the graph is a web graph comprising nodes and directed edges between respective ones of the nodes, the nodes corresponding to web pages and the directed edges corresponding to hyperlinks from one web page to another web page.

18. A method as recited in claim 16, wherein the method further comprises successively using the random numbers to update the graph by:

(A) adding an edge between a new object and an old object;

(B) adding an edge between two old objects;

or

(C) adding an edge from an old object to a new object according to configurable parameters α

, β and

γ

.

19. A method as recited in claim 16, wherein the method further comprises adding new edges to the graph as a function of directed preferential attachment.

20. A method as recited in claim 16, wherein the method further comprises generating the graph as a function of in-degree and/or out-degree shifts δ

_in and/or δ

_out.

21. A method as recited in claim 16, wherein the method further comprises modeling the graph as a function of a measured environmental characteristic that is based on a set of configurable parameters α

, β

, γ

, δ

_in, and δ

_out.

22. A method as recited in claim 16, wherein an in-degree power law associated with an object represented by the graph is different from an out-degree power law associated with the object.

23. A method as recited in claim 16, wherein an in-degree power law associated with an object represented by the graph is different from an out-degree power law associated with the object such that for a generator with parameters α

, β

, γ

, δ

_in and δ

_out, a proportion of vertices with in-degree equal to d_in asymptotically scales as follows;

24. A method as recited in claim 18, wherein (A) further comprises updating the graph by adding an edge from a new object v to a random old object w being chosen according to a probability distribution with

Pr(w=w_j)∝

(d_in(w_j)+δ

_in).

25. A method as recited in claim 18, wherein (B) further comprises updating the graph by adding an edge from a first existing object v of the graph to a second existing object w where the objects v and w are chosen according to a probability distribution with

Pr(v=v_i,w=w_j)∝

(d_out(v_i)+δ

_out)(d_in(w_j)+δ

_in).

26. A method as recited in claim 18, wherein (C) further comprises updating the graph by adding an edge from a randomly chosen old object w to a new object v, where w is chosen according to a probability distribution with

Pr(w=w_i)∝

d_out(w_i)+δ

_out.

27. A method as recited in claim 24, wherein (A) further comprises adding an edge E(i,j) from a new object v_i to an old object w_j by:

dividing interval [0, t+nδ

_in] into n slots of width d_in(w_j)+δ

_in;

selecting a random number r_in uniformly from the interval [0, t+nδ

_in]; and

selecting the old object w_j if the random number r_in falls into a j^th slot.

28. A method as recited in claim 25, wherein (B) further comprises adding an edge E(i,j) from an old object v_i to a second old object w_j by:

dividing the interval [0, t+nδ

_out] into n slots of width d_out(v_i)+δ

_out;

selecting a random number r_out uniformly from the interval [0, t+nδ

_out];

selecting the old object v_i if the random number r_out falls into an i^th slot;

dividing the interval [0, t+nδ

_in] into n slots of width d_in (w_j)+δ

_in;

selecting a random number r_in uniformly from the interval [0, t+nδ

_in]; and

selecting the old object w_j if the random number r_in falls into a j^th slot.

29. A method as recited in claim 26, wherein (C) further comprises adding an edge E(i,j) from an old object w_i to a new object v_j by:

dividing the interval [0, t+nδ

_out] into n slots of width d_out(w_i)+δ

_out;

selecting a random number r_out uniformly from the interval [0, t+nδ

_out]; and

selecting the old object w_i if the random number r_out falls into an i^th slot.

30. A method as recited in claim 16, wherein the method further comprises:

independently generating two random numbers λ

(v) and λ

(v) from specified distributions D_in and D_out for a new vertex v of the graph; and

utilizing the random numbers to update vertices of the graph as follows;

(A) choosing an existing vertex w according to λ

(w)(d_in+δ

_in) such that Pr(w=w_j)∝

λ

(w_j)(d_in(w_j)+δ

_in);

(B) choosing an existing vertex v according to μ

(v)(d_out+δ

_out) and a second existing vertex w according to λ

(w)(d_in+δ

_in), so that Pr(v=v_i, w=w_j)∝

μ

(v_i)λ

(w_j)(d_out(v_i)+δ

_out)(d_in(w_j)+δ

_in);

or

(C) selecting an existing vertex w according to μ

(w)(d_out+δ

_out) such that Pr(w=w_i)∝

μ

(w_i(d_out(w_i)+δ

_out).

31. A computing device for generating models of directed scale-free object relationships, the computing device comprising:

a processor; and

a memory coupled to the processor, the memory comprising computer-program instructions executable by the processor for;

generating a sequence of random numbers; and

successively selecting individual ones of the random numbers over time to generate models of directed scale-free object relationships in a graph, with the development of the graph depending on both in-degrees and out-degrees.

32. A computing device as recited in claim 31, wherein the graph is a web graph comprising nodes and directed edges between respective ones of the nodes, the nodes corresponding to web pages and the directed edges corresponding to hyperlinks from one web page to another web page.

33. A computing device as recited in claim 31, wherein the computer-program instructions further comprise instructions for successively using the random numbers to update the graph by:

(A) adding an edge between a new object and an old object;

(B) adding an edge between two old objects;

or

(C) adding an edge from an old object to a new object according to configurable parameters α

, β and

γ

.

34. A computing device as recited in claim 31, wherein the computer-program instructions further comprise instructions for adding new edges to the graph as a function of directed preferential attachment.

35. A computing device as recited in claim 31, wherein the computer-program instructions further comprise instructions for generating the graph as a function of in-degree and/or out-degree shifts δ

_in and/or δ

_out.

36. A computing device as recited in claim 31, wherein the computer-program instructions further comprise instructions for modeling the graph as a function of a measured environmental characteristic that is based on a set of configurable parameters α

, β

, γ

, δ

_in, and δ

_out.

37. A computing device as recited in claim 31, wherein an in-degree power law associated with an object represented by the graph is different from an out-degree power law power law associated with the object.

38. A computing device as recited in claim 31, wherein an in-degree power law associated with an object represented by the graph is different from an out-degree power law associated with the object such that for a generator with parameters α

, β

, γ

, δ

_in and δ

_out, a proportion of vertices with in-degree equal to d_in asymptotically scales as follows;

39. A computing device as recited in claim 33, wherein the computer-program instructions further comprise instructions based on (A) for updating the graph by adding an edge from a new object v to a random old object w chosen according to a probability distribution with

Pr(w=w_j)∝

(d_in(w_j)+δ

_in).

40. A computing device as recited in claim 33, wherein the computer-program instructions further comprise instructions based on (B), updating the graph by adding an edge from a first existing object v of the graph to a second existing object w where the objects v and w are chosen according to a probability distribution with

Pr(v=v_i,w=w_j)∝

(d_out(v_i)+δ

_out)(d_in(w_j)+δ

_in).

41. A computing device as recited in claim 33, wherein the computer-program instructions further comprise instructions based on (C) for updating the graph by adding an edge from a randomly chosen old object w to a new object v, where w is chosen according to a probability distribution with

Pr(w=w_i)∝

d_out(w_i)+δ

_out.

42. A computing device as recited in claims 33 and 39, wherein the computer-program instructions based’

on (A) further comprise instructions for adding an edge E(i,j) from a new object v_i to an old object w_j by;

dividing interval [0, t+nδ

_in] into n slots of width d_in(w_j)+δ

_in;

selecting a random number r_in uniformly from the interval [0, t+nδ

_in]; and

selecting the old object w_j if the random number r_in falls into a j^th slot.

43. A computing device as recited in claims 33 and 40, wherein the computer-program instructions based on (B) further comprise instructions for adding an edge E(i,j) from an old object v_i to a second old object w_j by:

dividing the interval [0, t+nδ

_out] into n slots of width d_out(v_i)+δ

_out;

selecting a random number r_out uniformly from the interval [0, t+nδ

_out];

selecting the old object v_i if the random number r_out falls into an i^th slot;

dividing the interval [0, t+nδ

_in] into n slots of width d_in(w_j)+δ

_in;

selecting a random number r_in uniformly from the interval [0, t+nδ

_in]; and

selecting the old object w_j if the random number r_in falls into a j^th slot.

44. A computing device as recited in claim 33 and 41, wherein the computer program instructions based on (C) further comprise instructions for adding an edge E(i,j) from an old object w_i to a new object v_j by:

dividing the interval [0, t+nδ

_out] into n slots of width d_out(w_i)+δ

_out;

selecting a random number r_out uniformly from the interval [0, t+nε

_out]; and

selecting the old object w_i if the random number r_out falls into an i^th slot.

45. A computing device as recited in claim 31, wherein the computer-program instructions further comprise instructions for:

independently generating two random numbers λ

(v) and μ

(v) from specified distributions D_in and D_out for a new vertex v of the graph; and

utilizing the random numbers to update vertices of the graph as follows;

(A) choosing an existing vertex w according to λ

(w)(d_in+δ

_in) such that Pr(w=w_j)∝

λ

(w_j)(d_in(w_j)+δ

_in);

(B) choosing an existing vertex v according to μ

(v)(d_out+δ

_out) and a second existing vertex w according to λ

(w)(d_in+δ

_in) so that Pr(v=v_i, w=w_j)∝

μ

(v_i)λ

(w_j)(d_out(v_i)+δ

_out)(d_in(w_j)+(δ

_in);

or

(C) selecting an existing vertex w according to μ

(w)(d_out+δ

_out) such that Pr(w=w_i)∝

μ

(w_i)(d_out(w_i)+δ

_out).

46. A computing device for generating models of directed scale-free object relationships, the computing device comprising:

means for generating a sequence of random numbers;

means for successively selecting individual ones of the random numbers over time to generate models of directed scale-free object relationships in a graph, with the development of the graph depending on both in-degrees and out-degrees.

47. A computing device as recited in claim 46, wherein the graph is a web graph comprising nodes and directed edges between respective ones of the nodes, the nodes corresponding to web pages and the directed edges corresponding to hyperlinks from one web page to another web page.

48. A computing device as recited in claim 46, and further comprising means for successively using the random numbers to update the graph by:

(A) adding an edge between a new object and an old object;

(B) adding an edge between two old objects;

or

(C) adding an edge from an old object to a new object, according to configurable parameters (α

, β and

γ

.

49. A computing device as recited in claim 46, and further comprising means for adding new edges to the graph as a function of directed preferential attachment.

50. A computing device as recited in claim 46, and further comprising means for generating the graph as a function of in-degree and/or out-degree shifts δ

_in and/or δ

_out.

51. A computing device as recited in claim 46, and further comprising means for modeling the graph as a function of a measured environmental characteristic that is based on a set of configurable parameters α

, β

, γ

, δ

_in and δ

_out.

52. A computing device as recited in claim 46, wherein an in-degree power law associated with an object represented by the graph is different from an out-degree power law power law associated with the object.

53. A computing device as recited in claim 46, wherein an in-degree power law associated with an object represented by the graph is different from an out-degree power law associated with the object such that for a generator with parameters α

, β

, γ

, δ

_in and δ

_out, a proportion of vertices with in-degree equal to d_in asymptotically scales as follows;

54. A computing device as recited in claim 48, and further comprising means based on (A) for updating the graph by adding an edge from a new object v to a random old object w chosen according to a probability distribution with

Pr(w=w_j)∝

(d_in(w_j)+δ

_in).

55. A computing device as recited in claim 48, and further comprising means based on (B), updating the graph by adding an edge from a first existing object v of the graph to a second existing object w where the objects v and w are chosen according to a probability distribution with

Pr(v=v_i,w=w_j)∝

(d_out(v_i)+δ

_out)(d_in(w_j)+δ

_in).

56. A computing device as recited in claim 48, and further comprising means based on (C) for updating the graph by adding an edge from a randomly chosen old object w to a new object v, where w is chosen according to a probability distribution with

Pr(w=w_i)∝

d_out(w_i)+δ

_out.

57. A computing device as recited in claim 48, and further comprising means based on (A) for adding an edge E(i,j) from a new object v_i to an old object w_j by:

dividing interval [0, t+nδ

_in] into n slots of width d_in(w_j)+δ

_in;

selecting a random number r_in uniformly from the interval [0, t+nδ

_in]; and

selecting the old object w_j if the random number r_in falls into a j^th slot.

58. A computing device as recited in claim 48, and further comprising means based on (B) for adding an edge E(i,j) from an old object v_i to a second old object w_j by:

dividing the interval [0, t+nδ

_out] into n slots of width d_out(v_i)+δ

_out;

selecting a random number r_out uniformly from the interval [0, t+nδ

_out];

selecting the old object v_i if the random number r_out falls into an i^th slot;

dividing the interval [0, t+nδ

_in] into n slots of width d_in (w_j)+δ

_in;

selecting a random number r_in uniformly from the interval [0, t+nδ

_in]; and

selecting the old object w_j if the random number r_in falls into a j^th slot.

59. A computing device as recited in claim 48, and further comprising means based on (C) for adding an edge E(i,j) from an old object w_i to a new object v_j by:

dividing the interval [0, t+nδ

_out] into n slots of width d_out(w_i)+δ

_out;

selecting a random number r_out uniformly from the interval [0, t+nδ

_out]; and

selecting the old object w_i if the random number r_out falls into an i^th slot.

60. A computing device as recited in claim 46, and further comprising means for:

independently generating two random numbers λ

(v) and μ

(v) from specified distributions D_in and D_out for a new vertex v of the graph; and

utilizing the random numbers to update vertices of the graph as follows;

(A) choosing an existing vertex w according to λ

(w)(d_in+δ

_in) such that Pr(w=w_j)∝

λ

(w_j)(d_in(w_j)+δ

_in);

(B) choosing an existing vertex v according to μ

(v)(d_out+δ

_out) and a second existing vertex w according to λ

(w)(d_in+δ

_in), so that Pr(v=v_i, w=w_j)∝

μ

(v_i)λ

(w_j)(d_out(v_i)+δ

_out)(d_in(w_j)+δ

_in);

or

(C) selecting an existing vertex w according to μ

(w)(d_out+δ

_out) such that Pr(w=w_i)∝

μ

(w_i(d_out(w_i)+δ

_out).