System and method for identifying key targets in a social network by heuristically approximating influence
One embodiment of the present invention provides a system for selecting a set of nodes to maximize information spreading. During operation, the system receives a budget constraint and a population sample, constructs a social network associated with the population sample, analyzes a network graph associated with the social network to obtain structural information associated with a node within the social network, estimates characteristics associated with the node, and selects the set of nodes that maximizes the information spreading under the budget constraint based on the structural information and the characteristics associated with the node.
1. A computer-executable method for delivering a message under a budget constraint, the method comprising:
receiving a population sample;
collecting data of online activities performed by users within the population sample;
constructing, by a server, a social network associated with the population sample based on the collected data, wherein the social network comprises a plurality of nodes, and wherein constructing the social network comprises applying a set of predetermined heuristic rules to the collected online activity data;
analyzing, by the server, a network graph associated with the social network to obtain structural information associated with a respective node within the social network;
determining, by the server, based on a Big-Five model and online activity data of a user associated with the node, a five-dimension vector that reflects personality traits of the user;
computing, by the server, an influence level of the node based on a combination of the structural information associated with the node and the five-dimension vector that reflects the personality traits of the user, wherein computing the influence level comprises applying a decision tree that is constructed based on the combination of the structural information and the five-dimension vector thereby enhancing an efficiency for computing the influence level;
identifying a set of nodes that maximizes the information spreading under the budget constraint based on computed influence levels of nodes within the social network; and
delivering, by the server over a computer network, the message to users associated with the set of identified nodes.
2. The method of claim 1 , wherein the structural information associated with the node includes centrality measures and an outreach ability, and wherein the centrality measures include one or more of: a degree-centrality measure, a betweenness-centrality measure, and a closeness-centrality measure.
3. The method of claim 1 , wherein identifying the set of nodes involves:
estimating an influence level associated with an initial node set; and
performing a greedy selection process to identify a node that maximizes a marginal gain of influence level to the initial node set.
4. The method of claim 3 , where estimating the influence level associated with the initial node set involves:
calculating a weighted sum of aggregated centrality measures associated with nodes within the initial node set;
calculating an outreach ability of the initial node set; and
calculating a weighted sum of aggregated characteristics associated with nodes within the initial node set.
5. The method of claim 3 , wherein estimating the influence level associated with the initial node set involves applying a machine-learning technique.
6. The method of claim 3 , wherein performing the greedy selection process involves determining whether a node number of the selected set exceeds a threshold determined by the budget constraint, and wherein the budget constraint includes one of: an amount of money, and a number of person hours.
7. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for delivering a message under a budget constraint, the method comprising:
receiving a population sample;
collecting data of online activities performed by users within the population sample;
constructing a social network associated with the population sample based on the collected data, wherein the social network comprises a plurality of nodes, and wherein constructing the social network comprises applying a set of predetermined heuristic rules to the collected online activity data;
analyzing a network graph associated with the social network to obtain structural information associated with a respective node within the social network;
determining, based on a Big-Five model and online activity data of a user associated with the node, a five-dimension vector that reflects personality traits of a user associated with the node;
computing an influence level of the node based on a combination of the structural information associated with the node and the five-dimension vector that reflects the personality traits of the user, wherein computing the influence level comprises applying a decision tree that is constructed based on the combination of the structural information and the five-dimension vector, thereby enhancing an efficiency for computing the influence level;
identifying a set of nodes that maximizes the information spreading under the budget constraint based on computed influence levels of nodes within the social network; and
delivering, over a computer network, the message to users associated with the set of identified nodes.
8. The computer-readable storage medium of claim 7 , wherein the structural information associated with the node includes centrality measures and an outreach ability, and wherein the centrality measures include one or more of: a degree-centrality measure, a betweenness-centrality measure, and a closeness-centrality measure.
9. The computer-readable storage medium of claim 7 , wherein identifying the set of nodes involves:
estimating an influence level associated with an initial node set; and
performing a greedy selection process to identify a node that maximizes a marginal gain of influence level to the initial node set.
10. The computer-readable storage medium of claim 9 , wherein estimating the influence level associated with the initial node set involves:
calculating a weighted sum of aggregated centrality measures associated with nodes within the initial node set;
calculating an outreach ability of the initial node set; and
calculating a weighted sum of aggregated characteristics associated with nodes within the initial node set.
11. The computer-readable storage medium of claim 9 , wherein estimating the influence level associated with the initial node set involves applying a machine-learning technique.
12. The computer-readable storage medium of claim 9 , wherein performing the greedy selection process involves determining whether a node number of the selected set exceeds a threshold determined by the budget constraint, and wherein the budget constraint includes one of: an amount of money, and a number of person hours.
13. A computer system for delivering a message under a budget constraint, comprising:
a processor; and
a memory coupled to the processor, wherein the memory stores a set of instructions that when executed by a computer cause the computer to perform a method, wherein the method comprises:
receiving a population sample;
collecting data of online activities performed by users within the population sample;
constructing a social network associated with the population sample based on the collected data, wherein the social network comprises a plurality of nodes, and wherein constructing the social network comprises applying a set of predetermined heuristic rules to the collected online activity data;
analyzing a network graph associated with the social network to obtain structural information associated with a respective node within the social network;
determining, based on a Big-Five model and online activity data of a user associated with the node, a five-dimension vector that reflects personality traits of a user associated with the node;
computing an influence level of the node based on a combination of the structural information associated with the node and the five-dimension vector that reflects the personality traits of the user, wherein computing the influence level comprises applying a decision tree that is constructed based on the combination of the structural information and the five-dimension vector, thereby enhancing an efficiency for computing the influence level;
identifying a set of nodes that maximizes the information spreading under the budget constraint computed influence levels of nodes within the social network; and
delivering, over a computer network, the message to users associated with the set of identified nodes.
14. The computer system of claim 13 , wherein the structural information associated with the node includes centrality measures and an outreach ability, and wherein the centrality measures include one or more of: a degree-centrality measure, a betweenness-centrality measure, and a closeness-centrality measure.
15. The computer system of claim 13 , wherein identifying the set of nodes involves:
estimating an influence level associated with an initial node set; and
performing a greedy selection process to identify a node that maximizes a marginal gain of influence level to the initial node set.
16. The computer system of claim 15 , wherein estimating the influence level associated with the initial node set involves:
calculating a weighted sum of aggregated centrality measures associated with nodes within the initial node set;
calculating an outreach ability of the initial node set; and
calculating a weighted sum of aggregated characteristics associated with nodes within the initial node set.
17. The computer system of claim 15 , wherein estimating the influence level associated with the initial node set involves applying a machine-learning technique.
18. The computer system of claim 15 , wherein performing the greedy selection process involves determining whether a node number of the selected set exceeds a threshold determined by the budget constraint, and wherein the budget constraint includes one of: an amount of money, and a number of person hour.