Abstract:
A method is provided for assigning user-centric importance ranks to database entries within the context of social networking. A database entry is assigned an importance rank with respect to a user based on the experiences of the user&#39;s social relations reachable in social graphs with the database entry or its related database entries. The assigned rank is dependent on the closeness of the user&#39;s social relations with the user and their authorities on the database entry. The closeness of relation between users is determined using information from social networking services. Importance ranks calculated from other methods may serve as initial estimates for the user-centric importance ranks. Moreover, a user may acquire more information about a database entry by either communicating with users having experiences with the entry or obtaining information from social networking services. The method improves search relevance and provides more personalized search results.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    Ser. No. 13/317,270, “A method for calculating distances between users in a social graph”, Oct. 13, 2011, pending, Zhijiang He 
         [0002]    Ser. No. 13/317,794, “A method for calculating proximities between nodes in multiple social graphs”, October 28, pending, Zhijiang He 
     
    
     FEDERALLY SPONSORED RESEARCH 
       [0003]    Not Applicable 
       SEQUENCE LISTING OR PROGRAM 
       [0004]    Not Applicable 
       US PATENT REFERENCES 
       [0005]    U.S. Pat. No. 6,285,999, “Method for node ranking in a linked database”, filed on Jan. 9, 1998, issued on Sep. 4, 2001, Lawrence Page 
       OTHER REFERENCES 
       [0006]    “Six degrees of separation”, http://en.wikipedia.org/wiki/Six_degrees_of_separation 
       FIELD OF THE INVENTION 
       [0007]    The present invention relates generally to techniques for search in a database. More specifically, it relates to methods for assigning user-centric ranks to database entries within the context of social networking. The entries in a database may or may not have linking relation. 
       BACKGROUND OF THE INVENTION 
       [0008]    Relevance has been consistently challenging in search. Due to the imperfect representation of a user&#39;s search intention in terms of keywords, the matched entries&#39; relevance to a user&#39;s search intention is hard to define. Various techniques have been applied to improving the relevance of search in a database. One of the most prominent is the PageRank algorithm used by Google, which remarkably ranks the nodes based on the relation between nodes in a linked database. The ranks of nodes are determined from the entries of the dominant eigenvector of a modified adjacency matrix representing the link structure of a linked database. 
         [0009]    Fundamentally, ranks in the PageRank algorithm are determined by the dominant eigenvalue of a modified adjacency matrix. Compared to the remaining eigenvalues of a modified adjacency matrix, the dominant eigenvalue is a first order approximation to the characteristics of a modified adjacency matrix. 
         [0010]    Moreover, regardless of individual users&#39; search intentions, the original PageRank algorithm assigns same rank to a node in a linked database. In some sense, the rank of a node may be relevant to the dominant search intention among all possible search intentions. 
         [0011]    Statistically, users&#39; search intentions may be characterized as, a distribution of probability. The dominant search intention represented by user-independent ranks is equivalent to mean of the probability distribution. For personalized search, ranks of the nodes may be further tuned according to the search histories of a user and his/her friends. For example, machine learning techniques may be used to predict the search characteristics and preferences of a user. 
         [0012]    However, the extent of search personalization based on a user&#39;s search history and his/her friends&#39; histories is limited. For instance, if the matched database entries and their related database entries are new to a user and his/her friends, the search results may be most likely determined by user-independent ranks. 
         [0013]    In recent years, social networking has become more and more popular. For instance, Facebook has more than half billion users. Large databases of social connections, i.e. social graphs, have been established. More importantly, according to the 6 degrees of separation, there may be on average 5 users between any two users of a popular social networking service. In other words, a user may easily connect to any other user on a popular social networking service. 
         [0014]    In real life, a user may ask his/her friends for an answer to a specific question. His/her friends may ask their friends for an answer to the question. In this real life example, friendship may be used to find an answer to a question. 
         [0015]    Similarly, social networking may bring new perspectives to personalized search in a database such as world wide web. Search in a database may be modeled as a process of knowledge propagation across relations in social graphs. It is assumed that some users may have already queried a database entry or its related database entries. It is further assumed that impact factors are defined to represent those users&#39; experiences with the database entry or its related database entries. The importance rank of a database entry with respect to a user is determined from the impact factors associated with users who may connect to the user in social graphs. 
         [0016]    A rank assigned to a database entry may represent a prediction of a user&#39;s level of interest, review, rating, opinion about the database entry. For instance, a user may query a database about dentists in a specific city. In this case, a rank assigned to a dentist entry with respect to a user may predict the user&#39;s level of interest, review, rating and opinion about the dentist. A larger rank assigned to a dentist may mean higher rating on the dentist. In other words, search relevance may include a user&#39;s possible level of interest, review, rating and opinion about a database entry. This may be an extended feature for search engines. 
         [0017]    Accordingly, it is an object of this invention to provide a method for assigning user-centric ranks to database entries within the context of social networking. 
       BRIEF SUMMARY OF THE INVENTION 
       [0018]    The present invention provides a method for assigning user-centric ranks to database entries within the context of social networking. Information of profiles, relations, groups, messages, etc., is obtained from social networking services with users&#39; permissions. The closeness of relation between users in a social graph may be determined from the obtained information. 
         [0019]    Social graphs represent social relations between users. The social relation between two users may carry a certain level of trust and credibility. Moreover, it may carry a certain level of similarity in search intentions. As a matter of fact, some search intentions may be triggered by communications between friends. Moreover, friends tend to have, similar interests and opinions. This serves as the foundation for ranking database entries with respect to a user according to the experiences of the user&#39;s social relations including but not limited to the user&#39;s direct friends with the database entries or their related database entries. 
         [0020]    To calculate the closeness of relation between nodes, in pending patent application Ser. Nos. 13/317,270 and 13/317,794, weighting factors are assigned to relations between users in a social graph. Weighting factors for relations in a social graph may be determined in various ways. In one embodiment of the pending patent application Ser. Nos. 13/317,270 and 13/317,794, weighting factors may be determined from the closeness of relation between two users. 
         [0021]    In pending patent application Ser. No. 13/317,270 and 13/317,794, distances/proximities of relation between users may be calculated from the weighting factors for relations in social graphs. The calculated distances/proximities describe the closeness of relation between users. 
         [0022]    To personalize search in a database, user-centric ranks for database entries with respect to a user may be used. Some assumptions need to be made when determining a user-centric rank for a database entry with respect to a user. It is assumed that some users connecting to a user in social graphs may have already queried a database entry or its related database entries. It is further assumed that impact factors for the database entry associated with those users may be derived from their experiences with the database entry or its related database entries. 
         [0023]    Based on the assumptions, a rank for a database entry with respect to a query user may be determined from the impact factors for this database entry associated with users connecting to the query user in social graphs. A rank for a database entry with respect to a query user may also be dependent on the closeness of relation between the query user and users having experiences with the database entry or its related database entries. The users connecting to the query user may have distinct authorities on the database entry. The user-centric rank for the database entry may be dependent on those users&#39; authorities on the database entry. Moreover, a query user may acquire more information about a database entry from users reachable from the query user in social graphs and having experiences with the database entry or its related database entries. 
         [0024]    If no user reachable from a user in social graphs has queried a database entry or its related database entries, a default user independent rank may be assigned to the database entry. Alternatively, a rank calculated from other approaches including PageRank, if available, may be assigned to the database entry. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0025]      FIG. 1  shows a diagram for a social friendship graph and a user database entry query relation graph in which a personalized search may be achieved by the search histories of a user&#39;s friends according to the invention. 
           [0026]      FIG. 2  shows a diagram for a social friendship graph and a user database entry query relation graph in which personalization by the search histories of a user&#39;s friends may fail according to the invention. 
           [0027]      FIG. 3  shows a conceptual view of a social graph according to the invention. 
           [0028]      FIG. 4  shows a diagram for a social friendship graph and a user database entry query relation graph according to the invention. 
           [0029]      FIG. 5  shows a social graph annotated with weighting factors, path proximities and proximities according to the invention. 
           [0030]      FIG. 6  shows a diagram for ranking database entries according to the invention. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0031]    In the following description, numerous specific details are set forth in order to provide a thorough understanding of the invention. It will be apparent to one skilled in the art, however, that the present invention may be practiced without these specific details. Accordingly, the following embodiments of the invention are set forth without any loss of generality to, and without imposing limitations upon, the claimed invention. 
         [0032]    To achieve the goal of personalized search, prior art may tune user-independent ranks for database entries according to the search histories of a user and his/her friends. This is demonstrated in  FIG. 1 . There are two graphs in  FIG. 1 . G 0  is a simplified social friendship graph. Not all friendship is shown in G 0 . User S has friend F i  where i ε [0, n−1]. G 1  represents query relations between users and database entries. A link between a user and a database entry in G 1  means the user has queried the database entry. In G 1 , e is a database entry matching S&#39;s search criteria. There are links between e and F x /P 0  in G 1 . The links mean that F x  and P 0  have queried e. In this case, a rank assigned to e with respect to S may be adjusted by F x &#39;s experience with e. 
         [0033]    However, personalization by search histories of a user and his/her friends may sometimes be less than perfect. As shown in  FIG. 2 , if an entry of interest to S has not been queried by any of S&#39;s friends, the personalization may fail, which is due to the limited size of S&#39;s friend circle. 
         [0034]    Given the limit of a user&#39;s friend circle size, a user&#39;s search intention may possibly be unique among his/her friends. In other words, the database entries which a user may be interested in may have not been queried by any of a user&#39;s friends. In this case, ranks of the database entries may not be tuned by the experiences of a user&#39;s friends. Thus personalization may fail in this case. Ideally, if everyone on Earth is a user&#39;s friend, then a user&#39;s search intention may always be shared by one of his/her friends. 
         [0035]    The popularity of online social networking services makes it possible to use the social graphs established by social networking services to achieve better personalization. According to the 6 degrees of separation, a user may connect to any other user in a popular social graph. A user may always share the same search intention as another user in social graphs.  FIG. 3  shows a conceptual view of a social graph. Each link in this graph is symbolic and may represent multiple links to other entities in this graph. P i  is one of the n users sharing S&#39;s search intention, where i ε [0, n−1]. S may be connected to the n users via a social graph. 
         [0036]    Like friendship in real world, social graphs obtained from social networking services may carry certain levels of trust and credibility. Moreover, The connections in social graphs may also carry certain levels of similarities in search intentions. Therefore, the social relations represented by social graphs may be used to assign user-centric ranks to entries in a database. 
         [0037]      FIG. 4  shows one embodiment of the present invention. There are two graphs G 0  and G 1  in  FIG. 4 . G 0  is a social graph. G 1  is a user database entry query relation graph. Not all relations are shown in G 0  and G 1 . e is one of the database entries matching S&#39;s search criteria. P 1 , P 4  and P 6  connect to e. It means P 1 , P 4  and P 6  have queried e. S&#39;s direct friend P 0  and P 2  have not queried e. As P 1  and P 4  are connected to S via P 0  and P 2  respectively, it is possible to personalize this specific search via the experiences of P 1  and P 4 . 
         [0038]    A user in a popular social graph may have hundreds of connections. Nonetheless, the connections may carry disparate levels of closeness. Family relation may carry a high level of similarity in search intentions. In another example, if there are more communications between two nodes, the relation between them may be closer as well. 
         [0039]    In one embodiment of the present invention, methods in pending patent application Ser. Nos. 13/317,270 and 13/317,794 may be used to calculate the closeness of relation between nodes in social graphs. Specifically, weighting factors are assigned to the relations in a social graph. Given a social graph G(V, E), V represents the set of nodes in G and E represents the set of edges connecting the nodes in V. For a relation e ij , w ij  is used to describe the closeness of relation from v i  to v j . The closeness of relation between nodes may be determined from the assigned weighting factors. 
         [0040]    One embodiment of the pending patent application Ser. No. 13/317,794 is shown in  FIG. 5 . It is a friendship graph G with user A, B and C. The weighting factors for relations between users are given in  FIG. 5 . The weighting factor for the relation from B to A w BA  is 0.2 while the weighting factor for the relation from B to C w BC  is 0.8. There is no direct relation between A and C. However, in real world, A may connect to C via B. In other words, relations may be propagated along a path connecting the two nodes. Moreover, the propagated relations may be attenuated during propagation. In pending patent application Ser. No. 13/317,794, the propagation attribute of this relation is defined to be attenuatable. Generally, social relations are attenuatable. 
         [0041]    In one embodiment of pending patent application Ser. Nos. 13/317,270 and 13/317,794, the weighting factors for attenuatable relations may be interpreted as a predetermined probability of selecting the next node from the current node&#39;s neighbors to traverse when searching a social graph. As the next node to visit is always one of v i &#39;s neighbors in a social graph, the sum of all weighting factors for relations sourced from v i  is 1. That is, 
         [0000]    
       
         
           
             
               
                 ∑ 
                 j 
               
                
               
                 w 
                 ij 
               
             
             = 
             1 
           
         
       
     
         [0042]    Apparently, w ij  and w ji  are not necessarily equal. For this reason, the original undirected G(V, E) is converted to a directed graph G′(V, W), where an edge e ij /e ji  in G is split into two directed edges w ij  and w ji  in G′. 
         [0043]    w ij  may be obtained from the closeness of social relation from v i  to v j  in a social graph. In one embodiment of the present invention, it may be derived from the communications between node v i  and v j . 
         [0044]    In pending patent application Ser. No. 13/317,794, proximities of relation between two nodes may be used to describe the closeness of relation between the two nodes in multiple graphs. If the proximity of relation from one node to another is large, the relation between them is close too. Proximities of relation may be calculated from the weighting factors for relations in social graphs. More specifically, the proximities of relation between two nodes may be determined from the weighting factors for relations on the paths connecting the two nodes. 
         [0045]    There may be a number of paths from a first node to a second node in a social graph. If the propagated relations between two nodes are attenuatable, path proximity may be defined to describe the propagated relations from the first node to the second node along a path. In one embodiment of pending patent application Ser. No. 13/317,794, proximity of attenuatable relation p ij  from node v i  to v j  is defined as 
         [0000]    
       
         
           
             
               p 
               ij 
             
             = 
             
               
                 max 
                 l 
               
                
               
                 pp 
                 ijl 
               
             
           
         
       
     
         [0000]    which is the maximum path proximity from v i  to v j . pp ijl  is the proximity for path l. Path l is one of the paths connecting v i  to v j . 
         [0046]    Similar to the asymmetry of weighting factors, proximities are asymmetric as well. Specifically, proximity p ij  may not be equal to p ji . 
         [0047]    The proximity of a path may be calculated from the weighting factors for relations on the path. Moreover, the probability of visiting node v j  from v i  following a path should be the multiplication of the probabilities for connections on the path. Therefore, in one embodiment of pending patent application Ser. No. 13/317,794, path proximity pp ijl  may be calculated as 
         [0000]      pp ijl =πw st  
 
         [0000]    where w st  is the weighting factor for the relation from v s  to v t  on path l connecting v i  to v j . 
         [0048]    The propagation of attenuatable relation across neighboring nodes should be an attenuating process. A propagation coefficient α is defined and should be in the interval of [0, 1]. Accordingly, in one embodiment of pending patent application Ser. No. 13/317,794, the path proximity pp ijl  may be defined as 
         [0000]      pp ijl =πw′ st  
 
         [0000]    where w′ st  is equal to α*w st  except for the last connection on the path. The w′ st  for the last connection on the path is equal to w st . 
         [0049]    The path proximities and proximities are shown in  FIG. 5 . Assuming propagation coefficient α is 0.373, the path proximity pp ABC =w AB *α*w BC =1.0*0.373*0.8=0.298. pp ABC  is the largest path proximity between A and C, therefore, p AC  is 0.298 as well. 
         [0050]    So far, the closeness of relation between users in social graphs may be determined. It should be noted that methods other than those presented in pending patent application Ser. Nos. 13/317,270 and 13/317,794 may also be used in the present invention to calculate the closeness of relation between users in social graphs. In one embodiment of the present invention, the minimum number of connections between users in social graphs may be used as an oversimplified metric to determine the closeness of relation between users. Next personalized ranking of database entries is addressed. 
         [0051]    Supposedly there are m entries matching S&#39;s search criteria, namely, e j , where j ε [0, m−1]. Each entry e j  has been assigned an initial rank r 0   j . In one embodiment of the present invention, it may be determined by other ranking methods such as PageRank. In another embodiment of the present invention, if r 0   j  is normalized to the interval of [0, 1], it may be assigned a mean value of the interval, i.e. 0.5. 
         [0052]    It is assumed that there are n j  users having experiences with e j  or its related database entries. In one embodiment of the present invention, each of the n j  users has a closeness of relation with S represented by proximity p Skj , where k ε [0, n j −1]. Each of the n j  users has an impact factor q kj  assigned for e j , which is determined from a user&#39;s experience with e j  or its related database entries. If a user is interested in e j  or its related database entries, he/she may spend a long time on e j  or its related database entries. If interested, a user may access e j  or its related database entries a number of times. An impact factor may also be determined from a user&#39;s level of interest, review, rating and opinion about a database entry or its related database entries. In one embodiment of the present invention, q kj  may be in the interval of [−1, 1], depending on whether a user has a positive or negative experience with e j  or its related database entries. If a user has no experience with e j  or its related database entries, q kj  may be zero. 
         [0053]    It is possible that two database entries may be related. As an oversimplified example, Italian cuisine and spaghetti are related. A person who likes Italian cuisine may like spaghetti as well. If a user has queried Italian cuisine, the user&#39;s experience with Italian cuisine may be used to predict his/her experience with spaghetti. Techniques including machine learning may be used to determine if two database entries are related. A user may not have queried a database entry. Nonetheless, the user&#39;s experience with one or more related database entries may be used to determine an impact factor for the database entry associated with the user. 
         [0054]    Moreover, a kj  is defined to represent the authority of user k on e j . In one embodiment of the present invention, if user k has expertise on e j , a kj  may be large. In another embodiment of the present invention, a kj  may be determined from information obtained from social networking services including but not limited to the profile, messages of user k. In yet another embodiment of the present invention, if the search intention of user k has a large probability of matching that of S, a kj  may be large as well. a kj  may also be derived from the number of times or frequencies search intentions of user k have matched search intentions of S. 
         [0055]    In one embodiment of the present invention, the problem of ranking e j  with respect to S may be formulated as: 
         [0000]        r   j   =f ( r   j   0   , p   S0j   , . . . , p   Sn     j     −1j   , q   −1j   , q   0j   , . . . , q   n     j     −1j   , a   −1j   , a   0j   , . . . , a   n     j     −1j ) 
         [0000]    Note that q −1j  represents a user&#39;s predicted impact factor for e j  and a −1j  represents the self authority of a user on e j . Both q −1j  and a −1j  may be derived from a user&#39;s search history of related database entries. 
         [0056]    There may be various ways to determine the implementation of function f. Techniques such as closed form representation, curve fitting, table lookup, etc., may be used to find a best solution. In one embodiment of the present invention, r j  may be determined as: 
         [0000]    
       
         
           
             
               r 
               j 
             
             = 
             
               
                 sin 
                 ( 
                 
                   π 
                   * 
                   0.25 
                   * 
                   
                     r 
                     j 
                     0 
                   
                   * 
                   
                     ( 
                     
                       1 
                       + 
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             
                               - 
                               1 
                             
                           
                           
                             
                               n 
                               j 
                             
                             - 
                             1 
                           
                         
                          
                         
                           
                             w 
                             kj 
                           
                           * 
                           
                             q 
                             kj 
                           
                         
                       
                     
                     ) 
                   
                 
                 ) 
               
               . 
             
           
         
       
     
         [0000]    In this embodiment of the present invention, rank r j   0  is normalized to [0, 1]. The sine function is used to convert the calculated value into a number within the interval of [0, 1]. w kj  represents the importance of q kj  and it is in the interval of [0, 1]. q kj  is within [−1, 1]. 
         [0057]    In one embodiment of the present invention, w kj  may be determined as a normalized product of a user&#39;s proximity and authority, as shown below: 
         [0000]    
       
         
           
             
               w 
               kj 
             
             = 
             
               
                 
                   p 
                   kj 
                 
                 * 
                 
                   a 
                   kj 
                 
               
               
                 
                   ∑ 
                   
                     i 
                     = 
                     
                       - 
                       1 
                     
                   
                   
                     
                       n 
                       j 
                     
                     - 
                     1 
                   
                 
                  
                 
                   
                     p 
                     ij 
                   
                   * 
                   
                     a 
                     ij 
                   
                 
               
             
           
         
       
     
         [0000]    For convenience of representation, p −1j  is used and is set to 1 in this embodiment of the present invention. 
         [0058]      FIG. 6  shows one embodiment of the present invention. There are two graphs in  FIG. 6 . G 0  is a social graph annotated with weighting factors, path proximities and proximities. A, B and C are directly connected to S, which means A, B and C are direct friends of S. D is not directly connected to S. Nonetheless, D is connected to S via C. G 1  is a user database entry query relation graph annotated with impact factors and authorities. Please note that not all relations are shown in G 0  and G 1 . 
         [0059]    Supposedly there are two entries e 0  and e 1  matching S&#39;s search criteria. The initial user independent ranking vector r 0  is [0.5, 0.3] T  for e 0  and e 1 . r 0   0 (0.5) is larger than r 1   0 (0.3). It means that most users may deem e 0  more important than e 1 . However, as shown in G 1 , S&#39;s direct friend A and C have negative experiences with e 0 . Moreover, D, who is indirectly connected to S, has a fairly positive experience with e 1 . Thus, it is expected that the personalization should rank e 1  higher than e 0 . In this example, it is assumed that S&#39;s self authorities on e 0  and e 1 , i.e. a −10  and a −11 , are 0. 
         [0060]    According to one embodiment of the present invention, r 0  may be calculated as: 
         [0000]    
       
         
           
             
               r 
               0 
             
             = 
             
               sin 
                
               
                 ( 
                 
                   π 
                   * 
                   0.25 
                   * 
                   
                     r 
                     0 
                     0 
                   
                   * 
                   
                     ( 
                     
                       1 
                       + 
                       
                         
                           
                             
                               p 
                               
                                 SA 
                                  
                                 
                                     
                                 
                                  
                                 0 
                               
                             
                             * 
                             
                               a 
                               
                                 A 
                                  
                                 
                                     
                                 
                                  
                                 0 
                               
                             
                             * 
                             
                               q 
                               
                                 A 
                                  
                                 
                                     
                                 
                                  
                                 0 
                               
                             
                           
                           + 
                           
                             
                               p 
                               
                                 SC 
                                  
                                 
                                     
                                 
                                  
                                 0 
                               
                             
                             * 
                             
                               a 
                               
                                 C 
                                  
                                 
                                     
                                 
                                  
                                 0 
                               
                             
                             * 
                             
                               q 
                               
                                 C 
                                  
                                 
                                     
                                 
                                  
                                 0 
                               
                             
                           
                         
                         
                           
                             
                               p 
                               
                                 SA 
                                  
                                 
                                     
                                 
                                  
                                 0 
                               
                             
                             * 
                             
                               a 
                               
                                 A 
                                  
                                 
                                     
                                 
                                  
                                 0 
                               
                             
                           
                           + 
                           
                             
                               p 
                               
                                 SC 
                                  
                                 
                                     
                                 
                                  
                                 0 
                               
                             
                             * 
                             
                               a 
                               
                                 C 
                                  
                                 
                                     
                                 
                                  
                                 0 
                               
                             
                           
                         
                       
                     
                     ) 
                   
                 
                 ) 
               
             
           
         
       
     
       That is 
       [0061]    
       
         
           
             
               r 
               0 
             
             = 
             
               sin 
                
               
                 ( 
                 
                   3.142 
                   * 
                   0.25 
                   * 
                   0.5 
                   * 
                   
                     ( 
                     
                       1 
                       + 
                       
                         
                           
                             0.2 
                             * 
                             0.3 
                             * 
                             
                               ( 
                               
                                 - 
                                 0.2 
                               
                               ) 
                             
                           
                           + 
                           
                             0.5 
                             * 
                             0.4 
                             * 
                             
                               ( 
                               
                                 - 
                                 0.5 
                               
                               ) 
                             
                           
                         
                         
                           
                             0.2 
                             * 
                             0.3 
                           
                           + 
                           
                             0.5 
                             * 
                             0.4 
                           
                         
                       
                     
                     ) 
                   
                 
                 ) 
               
             
           
         
       
     
         [0000]    r 0  is 0.222. 
         [0062]    Similarly, r 1  may be calculated as: 
         [0000]    
       
         
           
             
               r 
               1 
             
             = 
             
               sin 
                
               
                 ( 
                 
                   π 
                   * 
                   0.25 
                   * 
                   
                     r 
                     1 
                     0 
                   
                   * 
                   
                     ( 
                     
                       1 
                       + 
                       
                         
                           
                             p 
                             
                               SD 
                                
                               
                                   
                               
                                
                               0 
                             
                           
                           * 
                           
                             a 
                             
                               D 
                                
                               
                                   
                               
                                
                               1 
                             
                           
                           * 
                           
                             q 
                             
                               D 
                                
                               
                                   
                               
                                
                               1 
                             
                           
                         
                         
                           
                             p 
                             
                               SD 
                                
                               
                                   
                               
                                
                               0 
                             
                           
                           * 
                           
                             a 
                             
                               D 
                                
                               
                                   
                               
                                
                               1 
                             
                           
                         
                       
                     
                     ) 
                   
                 
                 ) 
               
             
           
         
       
     
       That is, 
       [0063]    
       
         
           
             
               r 
               1 
             
             = 
             
               sin 
                
               
                 ( 
                 
                   3.142 
                   * 
                   0.25 
                   * 
                   0.3 
                   * 
                   
                     ( 
                     
                       1 
                       + 
                       
                         
                           0.093 
                           * 
                           0.8 
                           * 
                           0.8 
                         
                         
                           0.093 
                           * 
                           0.8 
                         
                       
                     
                     ) 
                   
                 
                 ) 
               
             
           
         
       
     
         [0000]    r 1  is 0.412. 
         [0064]    In this example, personalized ranking vector r is [0.222, 0.412] T , which is different from initial ranking vector r 0 , i.e. [0.5, 0.3] T . The personalized ranks calculated by the present invention are consistent with the experiences of the users connecting to S in a social graph. 
         [0065]    In one embodiment of the present invention, the database entries&#39; information/links may be displayed as a directory listing. In another embodiment of the present invention, the search may be based on textual matching of user specified keywords. With the advancement of voice recognition technology, the search criteria may be derived from a user&#39;s voice. The calculated ranks may be displayed as well. Moreover, in one embodiment of the present invention, only impact factors associated with users having at least a minimum level of relation closeness with a query user are used in determining an assigned score. The minimum level of relation closeness may either be a default value or be specified by a query user. 
         [0066]    In one embodiment of the present information, the users associated with the impact factors used in calculating a user-centric rank may be listed. A path in social graphs connecting a query user and a user associated with an impact factor used in calculating a rank with respect to the query user may be listed as well. To acquire more information about a database entry, a query user may communicate with a user who is associated with an impact factor used in calculating a user-centric rank. In one embodiment of the present invention, the communication may be conducted using the communication facilities provided by social networking services such as email, messaging, etc. In another embodiment of the present invention, a query user may obtain information including messages regarding a database entry from social networking services with permissions. In yet another embodiment of the present invention, the impact factors used in calculating a user-centric rank may be constrained to the impact factors of a group. The group may either be created by a query user or be obtained from social networking services. 
         [0067]    When any information is disclosed, users&#39; privacies should be respected. If needed, users&#39; permissions should be obtained. 
         [0068]    It should be noted that the present invention may be applied to one or more social graphs obtained from one or more social networking services. If a user has accounts on multiple social networking services, these accounts may be linked to the same user. 
         [0069]    Unlike the PageRank algorithm, methods consistent with the present invention require no linking relation between database entries. The entries in a database may or may not have linking relation between them. For instance, a database may store advertisements to be delivered to users. In most cases, advertisements in an advertisement database may not have linking relation between them. The goal of a search is to find relevant advertisements that may be of interest to a user. Advertisements may be selected according to their user-centric ranks with respect to a user. 
         [0070]    Methods consistent with the present invention may be applied to a database that stores information about a document, an advertisement, a celebrity, a public figure, an artist, a band, a group, a company, a business, an organization, an institution, a place, an event, a brand, a product, a service, a buyer, a seller, etc. A user&#39;s impact factor for a database entry may be determined by the user&#39;s level of interest, review, rating and opinion on the database entry or its related database entries. A score assigned to a database entry with respect to a user may represent a prediction of the user&#39;s level of interest, review, rating and opinion on the database entry. 
         [0071]    The present invention has been disclosed and described with respect to the herein disclosed embodiments. However, these embodiments should be considered in all respects as illustrative and not restrictive. Other forms of the present invention could be made within the spirit and scope of the invention.