US6151585A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods and apparatus for determining or inferring influential rumormongers from resource usage data
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1998-04-24
•
Granted: 2000-11-21
•
Expires: 2018-04-24
Abstract
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.
Inventors
- 👤 Steven J. Altschuler
- 👤 Lani F. Wu
- 👤 David Ingerman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 22:23
CPC Classifications
G; G06; G06Q; G06Q30/00; G06Q30/02; G06Q30/0201; G06Q99/00
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
205 words
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.
Claim 2
Dependent Claim
205 words
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.
Claim 3
Dependent Claim
32 words
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.
Claim 4
Dependent Claim
38 words
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.
Claim 5
Dependent Claim
39 words
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.
Claim 6
Dependent Claim
117 words
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.
Claim 7
Dependent Claim
24 words
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.
Claim 8
Dependent Claim
37 words
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.
Claim 9
Dependent Claim
68 words
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.
Claim 10
Dependent Claim
18 words
The computer-implemented method of claim 8 wherein the observation length parameter is longer than the memory length parameter.
Claim 11
Dependent Claim
126 words
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.
Claim 12
Dependent Claim
24 words
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.
Claim 13
Dependent Claim
37 words
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.
Claim 14
Dependent Claim
65 words
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.
Claim 15
Dependent Claim
18 words
The computer-implemented method of claim 13 wherein the observation length parameter is longer than the memory length parameter.
Claim 16
Dependent Claim
131 words
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.
Claim 17
Dependent Claim
36 words
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.
Claim 18
Dependent Claim
27 words
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.
Claim 19
Dependent Claim
52 words
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.
Claim 20
Dependent Claim
47 words
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.
Claim 21
Dependent Claim
26 words
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.
Claim 22
Independent Claim
159 words
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.
Claim 23
Independent Claim
159 words
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.
Claim 24
Independent Claim
217 words
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.
Claim 25
Independent Claim
217 words
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.
Claim 26
Dependent Claim
21 words
The device of claim 22 wherein the influential rumormonger determination facility applies a greedy graph covering algorithm to the directed graph.
Claim 27
Dependent Claim
32 words
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.
Claim 28
Dependent Claim
32 words
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.
Claim 29
Dependent Claim
18 words
A medium containing machine readable instructions which, when executed by a machine, effect the method of claim 1.
References Cited (Backward Citations)
US5371673A
Cited
EP0397992A2
Cited
US5712985A
Cited
US5692178A
Cited
US5521814A
Cited
US5999192A
Cited
US6021403A
Cited
US6014628A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-11-21 | 2004-05-22 | 2004-11-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-11-21 | 2008-05-22 | 2008-11-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-11-21 | 2012-05-22 | 2012-11-21 | $7700.00 | Window Closed / Lapsed |