Methods and apparatus for determining or inferring influential rumormongers from resource usage data

• US 6,151,585 A
• Filed: 04/24/1998
• Issued: 11/21/2000
• Est. Priority Date: 04/24/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ingerman, David, Wu, Lani F., Altschuler, Steven J.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): ALLEN, AKIBA KANELLE
• Application Number:
  US09/065,970
• Time in Patent Office: 942 Days
• Field of Search: 705/10, 705/1, 705/500, 705/8, 705/9, 705/7
• US Class Current: 705/7.29
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: G06Q 99/00 Subject matter not provided for in other groups of this subclass

Abstract

Resource usage data is used to infer degrees of influence between users. Once such inferences are made, a directed graph representation of the users and the inferred "influence" between the users can be generated. "Influential rumormongers" can then be determined from the directed graph, for example, by using a greedy graph covering algorithm. In this way, marketing information can be targeted to "influential rumormongers" to optimize its dissemination and impact. If actual (explicit) data regarding the influence between users is known, such data may be used to refine or replace at least some edge values.

Claims

1. A computer-implemented method for ascertaining an influential rumormonger from amongst a plurality of users through a directed graph from resource usage log data including records having (i) user information, (ii) resource identification information, and (iii) resource request time information, the method comprising steps of:

a) inferring a corresponding measure of influence between each of a plurality of pairs of said users from the usage log data based on (i) the user information, (ii) the resource identification information, (iii) the resource request time information, and (iv) a memory length parameter so as to define a plurality of influence measures, wherein, for each of said pairs of users, one of the users in said each pair appears to exhibit influence, as reflected in said corresponding influence measure, over action taken by another one of the users in said one pair;

b) generating the directed graph having, for said each one of the pairs of users, first and second vertices corresponding to the one and the other one, respectively, of the users and having an edge connecting the first and second vertices and associated with the corresponding influence measure; and

c) determining the influential rumormonger from amongst the users and the influence measures provided in the directed graph.

2. The computer-implemented method of claim 1 wherein the step of determining the influential rumormonger from the directed graph is carried out by applying a greedy graph covering algorithm to the directed graph.

3. The computer-implemented method of claim 2 wherein the step of determining the influential rumormonger from the directed graph includes sub-steps of accepting at least one of an observation length parameter and (b) a number of rumor starters parameter.

4. The computer-implemented method of claim 1 wherein the step of determining the influential rumormonger from the directed graph includes sub-steps of accepting at least one of (a) an observation length parameter and (b) a number of rumor starters parameter.

5. The computer-implemented method of claim 1 wherein the step of inferring the corresponding influence measure includes sub-steps of, for all of the users, defining a user in the plurality of users as a first user and all other ones of the plurality of users as second users:

i) for all resources, if one of the second users requests a resource after the first user has requested the resource, then incrementing a first count, otherwise incrementing a second count; and

ii) inferring the corresponding influence measure between the first user, as said one user, and a corresponding one of the second users, as the other one of the users, based on the first count and the second count.

6. The computer-implemented method of claim 5 wherein the corresponding influence measure increases as a ratio of the first count to the second count increases.

7. The computer-implemented method of claim 5 further comprising the step of defining the corresponding influence measure by adding the first and second counts to generate a sum value, and dividing the first count by the sum value.

8. The computer-implemented method of claim 5 further comprising a step of:

c) determining the influential rumormonger from the directed graph by applying a greedy graph covering algorithm to the directed graph,

wherein the step of determining at least one influential rumormonger from the directed graph includes a sub-step of;

i) accepting at least one of (a) an observation length parameter and (b) a number of rumor starters parameter.

9. The computer-implemented method of claim 8 wherein the observation length parameter is longer than the memory length parameter.

10. The computer-implemented method of claim 1 wherein the step of inferring the corresponding influence measure includes sub-steps of, for all of the users, defining a user in the plurality of users as a first user and all other ones of the plurality of users as second users:

i) for all resources, if one of the second users requests a resource within a time period defined by the memory length parameter after the first user requested the resource, then incrementing a first count, otherwise incrementing a second count; and

ii) inferring the corresponding influence measure between the first user, as said one user, and a corresponding one of the second users, as the other one of the users, based on the first count and the second count.

11. The computer-implemented method of claim 10 wherein the corresponding influence measure increases as a ratio of the first count to the second count increases.

12. The computer-implemented method of claim 10 further comprising the step of defining the corresponding influence measure by adding the first and second counts to generate a sum value, and dividing the first count by the sum value.

13. The computer-implemented method of claim 10 further comprising a step of:

d) determining the influential rumormonger from the directed graph by applying a greedy graph covering algorithm to the directed graph, wherein the step of determining the influential rumormonger from the directed graph includes sub-steps of;

i) accepting at least one of (a) an observation length parameter and (b) a number of rumor starters parameter.

14. The computer-implemented method of claim 13 wherein the observation length parameter is longer than the memory length parameter.

15. The computer-implemented method of claim 1 wherein the step of inferring the corresponding influence measure includes sub-steps of, for all of the users, defining a user in the plurality of users as a first user and all other ones of the plurality of users as second users:

i) for all resources, incrementing a count if one of the second users requests a resource after the first user has requested the resource;

ii) summing counts, over all first users, associated with the second users to generate a sum associated with each of the second users; and

iii) determining the corresponding influence measure between the first user, as said one user, and a corresponding one of the second users, as the other one of the users, based on the counts and the sums.

16. The computer-implemented method of claim 15 wherein the corresponding influence measure between the one and the other one of the users increases as a ratio of the count associated with the users to the sum increases.

17. The computer-implemented method of claim 15 further comprising the step of defining the corresponding influence measure as the count associated with the users divided by the sum.

18. The computer-implemented method of claim 1, wherein, if the corresponding influence measure is known from explicit data, then further performing a step of:

d) setting the corresponding influence measure inferred in step (a) with to an influence measure between said one and the other one of the users known from explicit data.

19. The computer-implemented method of claim 1, wherein, if an influence measure between users in any one of said pairs of users is known from explicit data, then further performing a step of:

d) refining the corresponding influence measure based on the influence measure known from explicit data.

20. The computer-implemented method of claim 1 wherein the users are computers and the resources are separate instances of content available to the users via a network.

26. A medium containing machine readable instructions which, when executed by a machine, effect the method of claim 1.

21. A device for inferring an influential rumormonger from amongst a plurality of users from resource usage log data including records having (i) user information, (ii) resource identification information, and (iii) resource request time information, the device comprising:

a) a graph edge determination facility for determining a corresponding influence measure between each of a plurality of pairs of said users based on the user information, the resource identification information, the resource request time information, and a memory length parameter so as to define a plurality of influence measures, wherein, for each of said pairs of users, one of the users in said each pair appears to exhibit influence, as reflected in said corresponding influence measure, over action taken by another one of the users in said one pair; and

b) an influential rumormonger determination facility for determining the influential rumormonger based on the corresponding influence measures between all the pairs of said users, the users, and an observation length parameter.

22. A device for ascertaining an influential rumormonger from amongst a plurality of users through a directed graph from resource usage log data including records having (i) user information, (ii) resource identification information, and (iii) resource request time information, the method comprising steps of:

a) means for inferring [an) a corresponding measure of influence between each of a plurality of pairs of said users from the usage log data based on (i) the user information, (ii) the resource identification information, (iii) the resource request time information, and (iv) a memory length parameter so as to define a plurality of influence measures, wherein, for each of said pairs of users, one of the users in said each pair appears to exhibit influence, as reflected in said corresponding influence measure, over action taken by another one of the users in said one pair;

b) a graph generator for generating the directed graph having, for said each one of the pairs of users, first and second vertices corresponding to the one and the other one, respectively, of the users and having an edge connecting the first and second vertices and associated with the corresponding influence measure; and

c) an influential rumormonger determination facility for determining the influential rumormonger from amongst the users and the influence measures provided in the directed graph.

23. The device of claim 22 wherein the influential rumormonger determination facility applies a greedy graph covering algorithm to the directed graph.

24. The device of claim 23 wherein the influential rumormonger determination facility includes means for accepting at least one of (a) an observation length parameter and (b) a number of rumor starters parameter.

25. The device of claim 22 wherein the influential rumormonger determination facility includes means for accepting at least one of (a) an observation length parameter and (b) a number of rumor starters parameter.