Method and apparatus for targeting messages to users in a social network

Abstract

A method and apparatus for targeting messages to users in a social network, for example by first identifying topics in the social network is provided. One embodiment of a method for discovering topics in a social network includes collecting information from the social network, the information including at least one of: interactions between users of the social network or profile information for the users, determining a global topic model including at least one topic, based on the collected information, and locally refining the global topic model in accordance with the collected information.

What is claimed is: 
     
         1 . A method for grouping users of a computer network, the method comprising:
 algorithmically analyzing content of a first set of observed interactions among the users;   automatically inferring a topic, based at least in part on the algorithmically analyzing;   associating a subset of the users with the topic; and   determining a relative strength of a relationship between a first user and a second user in the subset of the users, wherein the relative strength is based at least in part on a quantitative measure of a second set of observed interactions involving the first user and the second user.   
     
     
         2 . The method of  claim 1 , wherein the first set of observed interactions includes electronic mail. 
     
     
         3 . The method of  claim 1 , wherein the first set of observed interactions includes an instant message. 
     
     
         4 . The method of  claim 1 , wherein the first set of observed interactions includes a posting to a web site, blog, or online forum. 
     
     
         5 . The method of  claim 1 , wherein the first set of observed interactions includes a comment or tag made on a web site or blog. 
     
     
         6 . The method of  claim 1 , wherein the algorithmically analyzing comprises:
 extracting a first word from the first set of observed interactions;   generating an initial topic by associating the first word with a second word;   associating at least some of the users with the initial topic, based at least in part on a similarity measure that relates the initial topic to profile information for the at least some of the users.   
     
     
         7 . The method of  claim 6 , wherein the automatically inferring comprises:
 calculating a centroid of the profile information, wherein the centroid is the topic.   
     
     
         8 . The method of  claim 6 , wherein the automatically inferring comprises:
 merging the initial topic with another topic.   
     
     
         9 . The method of  claim 1 , further comprising:
 refining the topic based, at least in part, on the first set of observed interactions.   
     
     
         10 . The method of  claim 9 , wherein the refining comprises:
 filtering the first set of observed interactions according to a criterion related to the topic;   adjusting a weight of a link relating a pair of interactions in the first set of observed interactions, in accordance with a result of the filtering; and   indicating the weight in a model of the topic.   
     
     
         11 . The method of  claim 10 , wherein the criterion is a frequency of appearance in the first set of observed interactions of a word related to the topic. 
     
     
         12 . The method of  claim 11 , wherein the adjusting comprises:
 setting the weight to a value that is proportional to the frequency.   
     
     
         13 . The method of  claim 10 , further comprising:
 dividing the topic into a plurality of sub-topics, based at least in part on the link.   
     
     
         14 . The method of  claim 1 , wherein the automatically inferring comprises:
 mapping the word into an ontology to produce a normalized set of concepts that defines the topic.   
     
     
         15 . The method of  claim 14 , wherein the ontology is community-generated. 
     
     
         16 . The method of  claim 1 , further comprising:
 obtaining a second third set of observed interactions among the users; and   dynamically updating the topic, based at least in part on the third set of observed interactions.   
     
     
         17 . The method of  claim 16 , wherein the dynamically updating is performed incrementally. 
     
     
         18 . The method of  claim 17 , wherein the dynamically updating comprises:
 filtering the third set of observed interactions according to a criterion related to the topic;   adjusting a weight of a link relating a pair of interactions in a cumulative set of interactions that includes the first set of interactions, the second set of interactions, and the third set of interactions, in accordance with a result of the filtering; and   indicating the weight in a model of the topic.   
     
     
         19 . The method of  claim 16 , wherein the dynamically updating comprises adjusting the relative strength. 
     
     
         20 . A computer-readable storage device having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to perform a method for grouping users of a computer network, comprising:
 algorithmically analyzing content of a first set of observed interactions among the users;   automatically inferring a topic, based at least in part on the algorithmically analyzing;   associating a subset of the users with the topic; and   determining a relative strength of a relationship between a first user and a second user in the subset of the users, wherein the relative strength is based at least in part on a quantitative measure of a second set of observed interactions involving the first user and the second user.