Patent ID: 7269628

Claim:
A method of providing common neighborhood analysis, the method comprising the steps of: determining a common neighborhood of selected Internet users sharing a set of common interests from a plurality of users; and predicting for a user in the common neighborhood of users a potential Internet website to visit from the website visits of at least one other user in the common neighborhood of users, wherein the common neighborhood is determined by: creating a set H of triples (b,c,v) where b, c, and v are vertices; sampling randomly a subset of H of a specified size into a set H′; creating a set C of points (a,b) that are a projection of a first two vertices of each triple in set H′; calculating a number of occurrences, N(a,b), for each pair of vertices within the set C; and sorting the C nondecreasingly by N(a,b), wherein the set C of points (a,b) represents the users in a common neighborhood, and the set E of edges represents the activities of the users within the common neighborhood; wherein the random sampling is determined by: creating an adjacency list E′; calculating a number of arcs connected to each vertex in a set V of vertices; calculating a prefix sum of a number of pairs of incident arcs N(a) for each node a up to and including a; generating random numbers uniformly from a set [1 . . . N]; sorting the generated random numbers into a list R; initializing a vertex index variable v to 1 and the set H′ to the empty set; incrementing the vertex index variable v by 1 until: N(v−1)<r<=N(v) for each random number r in the list R; selecting a vertex, a, from a set of vertices A(v) connected to vertex v; selecting a vertex, b, from a set of vertices A(v)−{v} connected to vertex v; adding a triple (a,b,v) to the set H′; and determining the set H′ when the vertex variable v is greater than a number of nodes N.