Abstract:
A method for discovering a group defined by a common characteristic is disclosed. The method includes building representation of a portion of a social network based on a starting person with the given characteristic, the person also providing the person&#39;s gender and school affiliation. The social network representation is then searched to discover clusters therein meeting certain size and connectivity requirements with respect to the network. After the clusters in the network are discovered, clusters having a high degree of similarity are merged together. The resulting clusters, both merged and non-merged, are then scored to determine the cluster that best fits the original group. The winning cluster is then returned to the starting person who confirms the correctness of the cluster. The set of the persons in a confirmed cluster are then displayed to the starting person.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This continuation application incorporates by reference in its entirety and claims the benefit of application, U.S. Ser. No. 13/624,971, filed on Sep. 24, 2012 and titled “SYSTEM AND METHOD FOR DISCOVERING GROUPS WHOSE MEMBERS HAVE A GIVEN ATTRIBUTE”. 
     
    
     FIELD OF THE INVENTION 
       [0002]    The present invention relates generally to discovering a group defined by a common attribute in a friend network. 
       DESCRIPTION OF THE RELATED ART 
       [0003]    A friend network can be viewed as a graph whose vertices are persons and whose edges indicate a friend relationship, F(v 1 , v 2 ). This graph can be exceedingly large and highly interconnected. The graph also contains auxiliary information about the friends in the graph, but this information is disjointed and unconnected in the graph. Thus, the graph is not, by itself, helpful in discovering groups of persons possessing a common attribute. For example, if one desires to know a group of persons in the graph who are members of an organization, there is no simple way to find this group directly from the graph. However, it is certainly desirable to use the friend network to groups having a common attribute for a variety of purposes. For example, it may be desirable to discover a group of persons all of whom have the same a common interest and to present this group to a party for marketing purposes. Thus, a problem with the friend graph exists in that it provides connectivity based on only one property, friendship, making it difficult to discover groups of people in the graph with a common attribute. 
       BRIEF SUMMARY OF THE INVENTION 
       [0004]    An embodiment solves the problem of finding groups of people in a friend network having a common characteristic. The embodiment performs this task extremely quickly and with a minimum of input information. One benefit of the present invention is that a group of persons for which a common attribute exists is now presentable for a variety of purposes. For example, if a merchant desires to sell goods or services to the group, then the discovery of the group is exceedingly valuable to the merchant. As another example, the discovered group can be used to increase social dynamics in a game or other application. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0005]    These and other features, aspects and advantages of the embodiments will become better understood with regard to the following description, appended claims, and accompanying drawings where: 
           [0006]      FIG. 1  depicts a sample friend network; 
           [0007]      FIG. 2  depicts input information from which a group may be discovered; 
           [0008]      FIG. 3  depicts an algorithm for discovering a group; 
           [0009]      FIG. 4  illustrates an algorithm for finding a cluster in a graph; 
           [0010]      FIG. 5  illustrates the merging process in  FIG. 3  in more detail; 
           [0011]      FIG. 6  is a system setting in which an embodiment is practiced; 
           [0012]      FIG. 7  is an example configuration of a server as depicted in  FIG. 6 ; 
           [0013]      FIG. 8  is an example configuration of a server place for a server as depicted in  FIG. 7 ; and 
           [0014]      FIG. 9  is an example configuration of a graphics processing unit. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0015]      FIG. 1  depicts a sample friend network. The network is an undirected graph having vertices representing people and edges representing a bidirectional friend relationship. A graph of this type can have many connections among vertices,  201 - 217 ,  251 - 265 , multiple groupings  102 ,  104 ,  106 ,  108 ,  110 ,  112 , and even disconnected groups  106 ,  108 ,  110 ,  112 . The popular site, Facebook, provides access, via an API, to a friend or social graph that includes hundreds of millions of people. In one embodiment, the Facebook social graph is accessed to construct an adjacency matrix for a graph on which further processing occurs. 
         [0016]      FIG. 2  depicts input information from which a group or organization may be discovered. In one embodiment, the input information is obtained from a person, hereinafter “the starting person,” who visits a website that is generally related to a group or organization in which the visiting person is a member. To register at the website the person offers his Facebook id  202  and permission to access the person&#39;s friend list  204  on Facebook. Along with this information, other information that normally accompanies a user object in Facebook, such as the user&#39;s name, the user&#39;s picture, the user&#39;s gender, the user&#39;s locale, and age range is available from the starting person. The Facebook ID provides input to an API to obtain the friend list for the given Facebook ID and from a subset  206  of the friend list id a friend list  208  is constructed. 
         [0017]      FIG. 3  depicts an algorithm for discovering a group in accordance with an embodiment of the present invention. In step  302 , the starting person&#39;s Facebook ID is obtained. In step  304 , through the starting person&#39;s Facebook id, the starting person&#39;s list of friends is obtained. Then, with this list, in step  306  the process uses a Facebook API to obtain the friends of each person in the list. In one embodiment, the Facebook API is a FQL API and the API queries a JSON-formatted list of the starting person&#39;s friends to obtain the friends of each person in the starting person&#39;s list. In another embodiment, the process divides the starting person&#39;s list of friends into a set of sublists, say with each sublist having 10 items, and issues multi-queries, with the sublist as a parameter, to obtain the friends of each person in the sublist, thereby reducing the number of queries needed and improving efficiency. The result of the queries is a network of friends centered on the starting person. The network contains only two degrees of friendship, counting from the starting person. In other words, only mutual friends of the starting person&#39;s friends are in the network. 
         [0018]    Also in step  306 , the process constructs an adjacency list to represent the network obtained from the queries. The adjacency list is a convenient data structure for representing the network in what follows. The adjacency list representation, in one embodiment, is a list of size |V|, the number of vertices in the network, with indexes into the edge list for each V, and then a list of size |E|, the number of edges, for the edges. For example, the vertex list is
       [index_v 0 , index_v 1 , index_v 2  . . . index_vn].
 
The edge list is
   [vertices connected to v 0 , vertices connected to v 1 ,   vertices connected to v 2 , . . . vertices connected to vn].
 
Thus, an index for a particular vertex in the vertex list provides a pointer to the portion of the edge list having vertices connected to the particular vertex. Alternatively, any data structure that can represent the network obtained from the queries will do. For example, an adjacency matrix is sufficient to represent the network.
       
 
         [0022]    The process then proceeds to construct the 2-neighbors for a given vertex after constructing the adjacency list. In one embodiment, the 2-neighbors are determined by visiting each 1-neighbor of a given vertex and determining if the 1-neighbor has a neighbor other than the particular vertex. If so, then this fact is recorded in a separate list. After all of the vertices of each 1-neighbor are visited, the list has all of the 2-neighbors of the given vertex. In one embodiment, the 1-neighbor list and the 2-neighbor list are bit maps. The 2-neighbors are used in the process of discovering clusters in the adjacency list. 
         [0023]    In step  308 , the process operates to discover any clusters present in the adjacency list. The clusters sought are the k-cores in the graph, where k-cores are collections of nodes that are internally dense and externally sparse. The algorithm for finding clusters is explained in more detail below. 
         [0024]    The search for clusters produces several or many clusters some of which are similar to each other. To handle these multiple similar clusters, the process constructs a convenient data structure for merging clusters that are similar to each other. In one embodiment, the data structure is a tree. In another embodiment, the data structure is a list. In the case of a tree structure, the process traverses in step  310  the tree from the bottom to the top, merging pairs of clusters that have a high degree of similarity. In the case of a list, the process traverses the list merging odd and even clusters. The merging occurs according to a criterion, which in one case is a relative cluster overlap threshold. If A and B are two clusters and the threshold is a value κ, then the relative cluster overlap criterion is that |A∩B|≧κ. Thus, the number of members in common must be at least κ. In one embodiment, the value κ is 3. 
         [0025]    When the merging process is completed, several merged clusters and possibly unmerged clusters remain. The process then determines the α and β coefficients for each remaining cluster. The merging process is described in more detail in connection with  FIG. 5 . 
         [0026]    Next, the process determines which of the clusters, merged or otherwise, corresponds to the group sought for. To find the best cluster, the process computes, in step  312 , a weighted sum function, 
         [0000]        w=w ( ms,gs,ss ,α,β),
 
         [0000]    for each cluster based on its α and β coefficients and any number of additional parameters. In one embodiment, the parameters include a gender score gs, a school score ss, and a member score ms, but any number of other parameters such as location, age, or last name of the family of the starting person can be included. In the above weighted sum function, the gender score is the fraction of members in the cluster having the same gender as the starting person. The school score is the fraction of members in the cluster attending the same school as the starting person. The member score is derived from a triangle distribution function with a range of [0,1] that is centered around the approximate size of the organization of which the starting person is a member. For example, if the size of the organization is 50, then the ms score is 
         [0000]        ms= 1−max(0,min|NumMembersInSameSchool−50|/50),
 
         [0000]    which computes a number between 0 and 1, depending on the number of members in the same school as the starting person. For example, if the number of members in the same school is 50, then the function has a value of 1. If the number of members in the same school is 0 or 100, then the score has a value of 0. In one embodiment, the weight sum calculation is =(1·ms+1·gs+1·ss+0.25·(1−α)+1·β), where the weights for ms, gs, and ss and β are unity and the weight for (1−α) is 0.25. 
         [0027]    The result of the weighted sum is a score and the cluster with the highest score is most likely the cluster sought after. The cluster with the highest core is then presented to the starting person, who then confirms that whether or not the cluster is correct, i.e., that it corresponds to a group of which the starting person is a member. If the cluster is not correct, the process presents to the starting person an alternative cluster, one that scored slightly lower, to find out if the alternative cluster is correct. If the cluster is correct, then those persons in the cluster other than the starting person are added to the site to which the starting person gave his Facebook id, so that the starting person can see all of the members of the group of which he or she is a member. 
         [0028]      FIG. 4  illustrates an algorithm for finding a cluster in a graph. The graph G has V vertices and E edges (G=(V, E)). A vertex vεV has a set of neighbors, denoted N(v) and the vertices that are r hops around the vertex are designated B r (v). Vertices within 2 hops of a given vertex are those in B 2  (V). The coefficient α refers to the degree of connectivity outside of a cluster and the coefficient β refers to the degree of connectivity within a cluster. A cluster C is considered internally dense if for each vertex in the cluster, the number of edges between it and any other vertex in the cluster is at least β*|C|, where |C| is the number of vertices in the cluster. A cluster c is externally sparse if for each vertex not in the cluster C, the number of edges between it and any other vertex in the cluster is at most α*|C|. When the β coefficient approaches unity, then the internal density is very high and the cluster is called a clique. When the a coefficient approaches zero, then the cluster is disconnected. Typically, a cluster has α&lt;β. The size of a cluster is denoted by s. The algorithm in  FIG. 4  starts, in step  410  with a given graph, G=(V, E) and desired α and β coefficients, along with the size s of the cluster desired to be found. After initializing the set to be returned, in step  414 , The algorithm then looks, in step  416 , at each vertex c in the graph and decides if the vertices v within a specified hop B r  (c) should be added, in step  422 , into a set that may become a cluster. The decision, in step  420 , for including the vertices within a specified hop into the set is whether the number of vertices in the intersection, computed in step  418 , of two neighborhoods is at least equal to a particular threshold, where the threshold is (2β−1)·s. In step  418 , one neighborhood is the one around the vertex c and the other neighborhood is the one around each vertex within the specified hop around the vertex c. Thus, if the two neighborhoods have sufficient vertices in common, as determined in step  420 , then the vertex c is included in the set, in step  422 , that may become a cluster. The set thus constructed becomes a candidate for a cluster and the candidate is then tested, in step  426 , for its alpha and beta coefficients. If the candidate passes the test, then it is output as a cluster. In one embodiment, the alpha coefficient is within a range of about 0 to 0.25 and the beta coefficient is within the range of about 0.75 to 0.85. 
         [0029]    In one embodiment, the algorithm illustrated in  FIG. 4  is processed on a graphics processing unit (GPU), such as the GeForce GTX 560, which has 336 internal processors. In this embodiment, the adjacency list is partitioned among the internal processors in the GPU, such that the internal processors concurrently build candidate clusters from each non-overlapping adjacency list portion. This permits the clusters in the adjacency list to be found in O(n 3 ) time, where n is the number of vertices in the adjacency list. 
         [0030]    In another embodiment, the algorithm illustrated in  FIG. 4  is processed via an adjacency list that has been compressed into a bit map in order to reduce the amount of memory required. A 5000-friend graph can be handled in about 3 Megabytes (MB). The conversion to bit maps reduces memory usage to O(n 2 /8), where n is the number of friends (vertices) in the graph. In this embodiment, not only is the adjacency list stored as a bit map, but the 2-neighbors are also stored as bit maps. 
         [0031]      FIG. 5  illustrates an embodiment of the merging process in more detail. In the figure, node r  502  is the root node of a tree whose leaves contain clusters, c 1   506 , c 2   508 , c 3   512 , and c 4   514 , found in the adjacency list. At node cm 1   504 , a test is performed to determine whether c 1   506  and c 2   508  are sufficiently similar that they should be merged. If so, then c 1   506  and c 2   508  are merged an entered into the cm 1   504  node. Similarly, a test is performed at node cm 2   510  to determine if clusters c 3   512  and c 4   514  are sufficiently similar to be merged. If so, then c 3   512  and c 4   514  are merged and entered into the cm 2   510  node. At the root node  502 , a test is performed to determine if the clusters at cm 1   504  and cm 2   510  are sufficiently similar to be merged. If so, the merged cluster is entered into the root node  502 . The result of this process is that there are fewer clusters to be considered in the next step of the process. 
         [0032]    In one embodiment, the merging process is performed on a Graphics Processing Unit (GPU), such as the GeForce GTX 560. In this embodiment, the multiple internal cores in the GPU operate in parallel to perform each stage of the merging and synchronize with each other before the next stage&#39;s processing is performed. For example, the merging of clusters c 1   506  and c 2   508  is performed in one core in the GPU while the merging of clusters c 3   512  and c 4   514  is performed in another core in the GPU. A synchronization is performed so that merging at the cr  502  node waits for the two cores to complete their respective operations. It is apparent that in a GPU with 336 internal cores, up to 336 different clusters can be merged concurrently, thereby significantly lowering the processing time for this operation. Additionally, in this embodiment, the alpha and beta coefficients (α, β) of the merged clusters are computed in parallel. 
         [0033]    In the GPU embodiment, the clusters and the merged clusters are stored as binary in the memory available to the GPU. 
         [0034]      FIG. 6  is a system setting  600  in which an embodiment can be practiced. The system setting, on which methods in accordance with the present invention operate, includes one or more client computing devices  602 ,  604 ,  606 ,  608 ,  610 , such personal computers  602 ,  604 , PDAs  608 , tablet computers  608 , or laptop computers  610 , a server  612 , that hosts a friend network and which is connected to a large database system  614 , and an application server  616 , which has access to a large storage system  618 . The client computing devices  602 - 610  and the servers  612 ,  616  are interconnected via an intranet or an internet  620 . In one embodiment, the internet is the Internet. 
         [0035]      FIG. 7  is an example configuration of a server  612 ,  614  as depicted in  FIG. 6 . The server  612 ,  616  includes one or more server blades  702   a  . . .  702   n , a local area network (LAN) interface  704  and a fiber interface  706 , which are interconnected via a blade interconnect  708 . In one embodiment, a blade interconnect  708  is a crossbar switch. The server blades obtain information, such as data and instructions, from either the LAN interface  704  or the fiber interface  706 . 
         [0036]      FIG. 8  is an example configuration of a server blade  702   a  . . .  702   n  for a server as depicted in  FIG. 7 . The server blade  702   a  . . .  702   n  includes one or more processors  802 , a memory  804 , a graphics processing unit (GPU)  810  such as a general purpose GPU (GPGPU), and a blade interface  806 , which are interconnected via a local bus  808 . The processors  802  typically have instruction set architectures. The memory  804  is typically a non-transitory repository for program instructions on which the processor  802  operates. The program instructions in the memory  804  are typically loaded through the blade interface  806  from a large storage array connected to the server blade  702   a  . . .  702   n  via the LAN interface  704  or fiber interface  706 . Thus, the program instructions that are executed by the processors  802  in the server blades are stored in a non-transitory computer-readable medium such as a large storage array. In one embodiment, the large storage array is a RAID-array or an array of non-rotating, silicon disk drives. 
         [0037]    In one embodiment, the GPGPU, shown in  FIG. 9 , includes up to up to 6 Gigabytes of DRAM  902 , L2 cache  908  and  512  cores, where a core executes one integer or floating-point instruction per clock for a thread. The cores are organized into blocks of 32 cores, which are in turn organized into to grids of 16 blocks. Each core has its own, private local memory, each block has its own, shared memory, and each grid has access to global memory. The 512 cores are thus organized into 16 streaming multiprocessors (SM)  904   a - p , each having 32 cores. A scheduler  906  in the GPU distributes a block of threads to each of the streaming multiprocessors  904   a - p , which then dispatches the threads to each of its 32 cores. Thus, if a task permits it, a GPU can execute up to 512 threads, concurrently. 
         [0038]    Although the present invention has been described in considerable detail with reference to certain preferred versions thereof, other versions are possible. Therefore, the spirit and scope of the appended claims should not be limited to the description of the preferred versions contained herein.