US0074721 1 OB2
`
`(12) United States Patent
`Achlioptas
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7472,110 B2
`Dec. 30, 2008
`
`(54) SYSTEMAND METHOD FOR EMPLOYING
`SOCIAL NETWORKS FOR INFORMATION
`DISCOVERY
`
`(75) Inventor: Dimitris Achlioptas, Seattle, WA (US)
`(73) Assignee: Microsoft Corporation, Redmond, WA
`(US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 411 days.
`(21) Appl. No.: 10/353,623
`
`(*) Notice:
`
`(22) Filed:
`
`Jan. 29, 2003
`
`(65)
`
`Prior Publication Data
`US 2004/O 148275A1
`Jul. 29, 2004
`
`(51) Int. Cl.
`(2006.01)
`G06F 7/30
`(52) U.S. Cl. ............................................. 707/3; 707/10
`(58) Field of Classification Search ................. 707/13,
`707/9; 705/26, 27, 7
`See application file for complete search history.
`References Cited
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`6,115,709
`6,269,369
`6,487,541
`6,681,108
`6,714,916
`6,970,879
`7,031,952
`7, 177,880
`2002/0169737
`2002/01781.61
`2002fO1941.78
`2004/OO32393
`2004.0068477
`2004/011 1386
`2004/O122803
`
`9/2000 Gilmour et al. ................ 707/9
`A
`7/2001 Robertson
`B1
`1 1/2002 Aggarwal et al.
`B1
`1/2004 Terry et al.
`B1
`3, 2004 Robertson et al.
`B1
`B1 * 1 1/2005 Gilmour ..................... 707/102
`B1
`4/2006 Heumann et al. .............. 707/1
`B2
`2/2007 Ruvolo et al.
`A1 * 1 1/2002 Armstrong et al. ............ 7O6/59
`Al 1 1/2002 Brezin et al. .................. 707/10
`Al 12/2002 Gilmour et al. ................ 707/9
`A1* 2/2004 Brandenberg et al. ....... 345,156
`Al
`4/2004 Gilmour et al. ................ 707/1
`A1* 6/2004 Goldberg et al. ............... 707/1
`Al
`6/2004 Domet al. ..................... 707/3
`
`2004/O122855 A1
`
`6/2004 Ruvolo et al.
`
`OTHER PUBLICATIONS
`
`Henry Kautz, et al.; "Combining Social Networks and Collaborative
`Filtering”. Communications of the AMC, Mar. 1997, pp. 63-65, vol.
`40, No. 3.
`Henry Kautz, et al.; “The Hidden Web”, 1997, pp. 27-36.
`Henry Kautz, et al.; “Creating Models of Real-World Communities
`with Referral Web. 1998.
`Jon Kleinberg; “The Small-World Phenomenon: An Algorithmic Per
`spective”, 2000, pp. 1-14.
`M.E.J. Newman: “Small Worlds: The Structure of Social Networks',
`2000, pp. 1-8.
`John Schneider, et al., “Disseminating Trust Information in Wearable
`Communities”, 2000, pp. 1-5.
`(Continued)
`Primary Examiner Don Wong
`Assistant Examiner Sheree N Brown
`(74) Attorney, Agent, or Firm Amin, Turocy & Calvin, LLP
`
`(57)
`
`ABSTRACT
`
`Systems and methods are provided that enable searches of
`Social networks by acting as a “compass” that assists users in
`navigating the Social network. Individual userparticipation is
`not required in response to queries from other users. The
`systems and methods offer navigational assistance or infor
`mation as opposed to a traditional search which returns
`requested information, thus currently acceptable Social
`mechanisms for arbitrating trust can be exploited. As a result,
`users do not make their personal information publicly search
`able, while at the same time, they are protected from potential
`misrepresentations of facts.
`
`25 Claims, 16 Drawing Sheets
`
`100 \
`
`
`
`20
`
`
`
`4)
`- ió - -
`COMPONENT
`
`privacy
`coMPONENT
`
`QUERY RESULTS
`
`:
`
`PARSER
`
`NDEX 5-108
`COMPONENT
`SEARCHENGINE
`
`

`

`US 7472,110 B2
`Page 2
`
`OTHER PUBLICATIONS
`Alfarez Abdul-Rahman, et al.; “Supporting Trust in Virtual Commu-
`nities', 2000.
`David W. McDonald, et al.: “Just Talk to Me: A Field Study of
`Expertise Location”, Nov. 14-18, 1998, pp. 1-10.
`Keith N. Hampton, et al.; “Netville On-line and Off-line'. American
`Behavioral Scientist, Nov. 1999, pp. 475-492, vol.43, No. 3.
`
`Emmanuel F. Koku, et al.; "Scholarly Networks as Learning Com
`munities: The Case of TechNet'. Jan. 2002, pp. 1-36.
`Valdis Krebs; “The Social Life of Routers: Applying Knowledge of
`Human Networks to the Design of Computer Networks'. The
`Internet Protocol Journal, Dec. 2000, pp. 15-25, vol. 3, No. 4.
`
`* cited by examiner
`
`

`

`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 1 of 16
`
`US 7472,110 B2
`
`0 II
`
`
`
`
`
`| |
`
`|
`
`
`
`| SGHTI HOHd
`
`YIEIST)
`
`> 00 I
`
`I ’5) ILI
`
`
`
`SLTIOSOETH AHRQ?)
`
`

`

`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 2 of 16
`
`US 7472,110 B2
`
`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 2 0f 16
`
`US 7,472,110 B2
`
`CON
`
`
`
`FIG.2
`
`TTI-1023, Page 4
`
`

`

`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 3 of 16
`
`US 7472,110 B2
`
`
`
`
`
`
`
`JLN EINOd?VNOC)
`
`
`
`{{OVYHOLS EILVATHd
`
`
`
`
`
`90€
`
`
`
`EINIONGH HORÐVEIS
`
`9 °5)IH
`
`Z09)
`
`

`

`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 4 of 16
`
`US 7472,110 B2
`
`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 4 0f 16
`
`US 7,472,110 B2
`
`a
`
`500
`k
`
`G.)
`9
`
`lf C
`mU
`
`h—i
`LE
`
`v
`Y
`C:
`1—4
`C9
`F31
`u
`s
`
`TTI-1023, Page 6
`
`8'
`VI'
`
`rs
`
`9 » Q A
`c) ,
`)
`S
`
`3
`Yr
`
`w
`
`cLI
`
`If
`
`OI
`
`o
`
`n"
`
`d
`
`0“
`C
`
`

`

`U.S. Patent
`
`80020“,3mD
`
`mS
`
`61f0
`
`11,274,7SU
`
`2
`
`Bo0e05H
`
`wow
`
`
`
`5mgwgmMmE/AUZNngmflm
`
`
`NE
`
`MOZOHH<EMOHHZH
`
`mmgg<
`
`mcw
`
`Noe
`
`TTI-1023, Page 7
`
`
`

`

`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 6 of 16
`
`US 7472,110 B2
`
`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 6 0f 16
`
`US 7,472,110 B2
`
`s
`v
`
`
`
`700
`/
`
`FIG.7
`
`TTI-1023, Page 8
`
`E 2
`
`s
`2
`s
`
`>
`
`

`

`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 7 0f 16
`
`US 7,472,110 B2
`
`vow
`
`v/l
`
`New
`
`
`
`mquEm;BmmfiU
`
`mHmOmm
`
`UZFDmAAOU@2435
`
`mammom
`
`
`
`@3266Omnm>
`
`
`
`EOZOmHm<mbmmmmté
`
`
`
`mn—mELMmL/IAOUQmMMOmmEME
`
`mfi<m
`
`
`
`mSZO0mm?»NE
`
`3240OmQSom<MOmmEmE
`
`
`
`mg
`
`
`
`mHOZEd
`
`OC<UE~U
`E
`
`w.9:—
`
`TTI-1023, Page 9
`
`
`
`

`

`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 8 of 16
`
`US 7472,110 B2
`
`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 8 0f 16
`
`US 7,472,110 B2
`
`'a
`’{r-IOOO
`
`
`
`FIG.10
`
`
`
`FIG.9
`s
`
`TTL1023,Page10
`
`

`

`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 9 of 16
`
`US 7472,110 B2
`
`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 9 0f 16
`
`US 7,472,110 B2
`
`HEROES
`
`FANS
`
`2
`
`FIG.11
`
`TTL1023,Page11
`
`

`

`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 10 of 16
`
`US 7472,110 B2
`
`oozi ?*
`
`90ZI
`
`
`
`
`
`YHO LVNÍCTRIOOO
`
`ZI "OIH
`
`

`

`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 11 of 16
`
`US 7472,110 B2
`
`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 11 0f16
`
`US 7,472,110 B2
`
`‘r//,—1300
`
`
`
`FIG.13
`
`TTI-1023, Page 13
`
`

`

`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 12 of 16
`
`US 7472,110 B2
`
`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 12 0f 16
`
`US 7,472,110 B2
`
`5
`
`1406
`
`1404
`
`S.
`
`1402
`
`s
`1408f1400
`
`FIG.14
`
`TTI-1023, Page 14
`
`

`

`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 13 of 16
`
`US 7472,110 B2
`
`
`
`1502
`
`RECEIVE INFORMATION
`RELATING TO
`INDIVIDUAL OR ENTITY
`
`
`
`1504
`
`
`
`NEW INDIVIDUAL OR
`ENTITY?
`
`1506
`
`1508
`
`1510
`
`ADD INDIVIDUAL OR
`ENTITY TO SOCIAL
`NETWORK
`
`
`
`
`
`
`
`
`
`ADD NEW ARCS
`
`UPDATE FAMILLARITIES
`
`
`
`ADD NEW ARCS
`
`UPDATE
`ATTRIBUTES
`
`1so
`
`F.G. 1S
`
`

`

`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 14 of 16
`
`US 7472,110 B2
`
`1602
`
`USER GENERATES
`QUERY
`
`SEARCHDIRECTED - 1604
`GRAPH
`
`
`
`
`
`1606
`
`
`
`1608
`
`REQUESTED
`INFORMATION FOUND"?
`
`NO
`
`NOTIFY USER OF
`FAILURE
`
`YES
`
`GENERATE REFERRAL
`PATHS
`
`1610
`
`
`
`EXPOSE PORTION OF
`OPTIMAL PATH TO USER
`
`1612
`
`USER MAKES REQUEST
`TO EXPOSED NOTDE OF
`OPTIMAL PATH
`
`1614
`
`1616
`
`
`
`
`
`Y-1600
`
`EXPOSED NODE
`COOPERATES
`
`
`
`EXPOSE NEXT
`NODE IN PATH
`
`NO
`
`68
`
`YES
`
`
`
`PATH AVAILABLE2
`
`FIG. 16
`
`

`

`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 15 of 16
`
`US 7472,110 B2
`
`PROCESSING
`UNIT
`
`SYSTEM
`1718 MEMORY
`
`1714
`1716
`
`1722
`
`1720
`
`ROM r
`
`-
`- - - - -6. 1740
`OPERATING SYSTEM
`: r ----4--.
`; : APPLICATIONS:
`A 1744
`7.
`MODULES
`- -
`- - -
`f----
`:----P----
`
`- - -
`
`1734 - 7 C-1724
`61-1728
`
`ILARD DRIVE
`
`1726
`
`INTERFACE
`
`
`
`3.
`
`1730
`1732
`
`MONITOR
`
`754
`
`1748
`
`KEYBOARD
`1750 N
`
`MOUSE
`
`REMOTE
`COMPUTER(S)
`
`LAN
`
`1762
`
`MEMORY
`STORAGE
`
`INTERFACE
`
`MODEM
`
`F.G. 17
`
`1758
`
`1760
`
`

`

`U.S. Patent
`
`Dec. 30, 2008
`
`Sheet 16 of 16
`
`US 7472,110 B2
`
`1810
`
`
`
`CLIENT(S)
`
`1800
`
`1830
`
`SERVER(S)
`
`CLIENT
`DATA
`STORE(S)
`
`
`
`
`
`
`
`
`
`
`
`SERVER
`DATA
`STORE(S)
`
`
`
`COMMUNICATION
`FRAMEWORK
`
`F.G. 18
`
`

`

`US 7,472,110 B2
`
`1.
`SYSTEMAND METHOD FOR EMPLOYING
`SOCIAL NETWORKS FOR INFORMATION
`DISCOVERY
`
`TECHNICAL FIELD
`
`The present invention relates generally to information net
`works, and more particularly to employing Social networks
`for information discovery.
`
`BACKGROUND OF THE INVENTION
`
`10
`
`2
`individuals due in large part to the relative size of the indi
`vidual’s Social network, time constraints, taxing of respective
`relationships within the Social network (e.g., frequent
`requests for information can have a negative impact on a
`relationship), etc.
`A number of approaches have been conventionally
`employed to obtain social opportunities and information from
`Social networks. One approach that can be used is for a person
`to email everyone he or she knows (e.g., buddies) requesting
`information on a particular Subject. This approach is not
`likely to be appreciated by individuals on the receiving end of
`the email, particularly if such approach is employed often;
`and could possibly damage personal relationships.
`Another technique to utilizing social information from
`Social networks is to have individuals create a "home page'
`about themselves in which they describe particular attributes
`by which they want to be referred to, such as place of birth,
`high-school attended, occupation, areas of expertise, inter
`ests, hobbies, plans for the Summer and the like. These pages
`can be associated with a search engine—then, in response to
`a person with certain attributes, the requested information,
`possibly including contact information, is returned. This
`approach fails for a number of reasons. Referrals often rely on
`information that individuals do not wish to be make publicly
`searchable. For example, typically individuals prefer not to
`have strangers and telemarketers be able to determine what
`their friends know about them, such as their hobbies and
`favorite vacation spots. Additionally, people identified
`through such a search can be strangers and unreliable. For
`example, a search for someone to carpool with may return an
`individual with a matching work schedule, but that individual
`could be difficult to get along with.
`Thus, Social networks and their direct personal relation
`ships include a tremendous amount of latent information and
`opportunities. However, conventional approaches for discov
`ering these latent features fail to properly utilize Social net
`works in that they:
`i) overtax personal relationships and cause information
`overload; and/or
`ii) are inadequate for maintaining a Sufficient level of indi
`vidual privacy.
`
`15
`
`25
`
`30
`
`35
`
`40
`
`One of the most effective channels of disseminating and
`obtaining information is through direct, personal relation
`ships referred to as Social networks. A social network consists
`of individuals and their personal relationships to other indi
`viduals through which social information and opportunities
`are exchanged. The direct, personal relationship implies that
`two people “know each other and typically have a certain
`amount of trust for each other. The value of social networks
`can be demonstrated for example by the “six degrees of
`separation’ phenomenon, which means that the distance
`between any two individuals in terms of direct personal rela
`tionships is relatively small (e.g., 6 degrees or less). Social
`networks are frequently employed by individuals often with
`out conscious thought. For example, a person may be search
`ing for a job and contact his or her friends to determine if they
`are aware of available positions. These friends are able to
`provide reliable information about positions they themselves
`directly know about. Additionally, these friends can recom
`mend their job-seeking friend for available positions, assum
`ing they consider the job-seeking friend to be qualified, reli
`able, hard working and the like. Furthermore, these direct
`personal relationships can be employed to obtain social infor
`mation and/or opportunities such as for example information
`about possible romantic partners, good movies, restaurants,
`buying, selling, buing or trading of items and services, rec
`ommendations for movies, restaurants, romantic partners and
`the like.
`Direct personal relationships are particularly useful in
`obtaining information and opportunities because of the asso
`ciated reliability of information and individuals involved. For
`example, an individual typically is more often willing to Swap
`a vacation home (house-swap) with a friend of a friend, even
`though the individual may not personally know the friend of
`45
`a friend, than to house-swap with a stranger. A basis for Such
`trust is that the individual can trust that their immediate friend
`would not be associated with the person offering to house
`swap (e.g., friend of the friend) were the friend of a friend not
`reliable or trustworthy. (Or, more generally, the immediate
`friend can be trusted to offer an honest assessment of the
`trustworthiness of the third party.) Social networks are often
`relied upon for opinion based information Such as for
`example, movies, restaurants, travel locations and the like.
`Such information within a large number of the general popu
`lous is typically more relied on than well known restaurant
`and movie critics.
`However valuable social networks are, they can be
`extremely difficult to utilize in that it can be time consuming
`for an individual to contact every person they have a relation
`ship with when searching for information. Moreover, even if
`an individual could make the searching task easier for them
`selves, e.g. by creating a massive mailing list of their friends,
`addressing everyone in that list for each question is highly
`antisocial and certainly unsustainable as a collective behav
`ior, i.e. if everyone does it. In general, such type of manual
`searching through a social network is impracticable for most
`
`SUMMARY OF THE INVENTION
`
`The following presents a simplified Summary of the inven
`tion in order to provide a basic understanding of some aspects
`of the invention. This summary is not an extensive overview
`of the invention. It is not intended to identify key/critical
`elements of the invention or to delineate the scope of the
`invention. Its sole purpose is to present some concepts of the
`invention in a simplified form as a prelude to the more
`detailed description that is presented later.
`The present invention relates to systems and methodolo
`gies that facilitate maintaining privacy of personal informa
`tion within public database search environments. The inven
`tion also can facilitate conducting general queries of
`databases for purposes of locating personal attribute informa
`tion of an unknown person, and allow an originator of a query
`to evaluate a level of trust associated with an individual iden
`tified by a query. Moreover, the invention has an effect of
`providing for a private database that is publicly searchable in
`part due to masking properties (e.g., not associating query
`results with direct exposure of individuals that may be part of
`the query results) of the present invention.
`The present invention leverages efficiencies and process
`ing power associated with modern computing systems so as to
`expand a scope of human social networks beyond what is
`
`50
`
`55
`
`60
`
`65
`
`

`

`3
`conventionally practicable with respect to Solely human
`based social networking. In other words, the Subject invention
`provides a computer based search system/methodology that
`maps or models human Social networks and exposes untapped
`Social opportunities (e.g., connecting individuals) at a scale
`and granularity not achievable by conventional search sys
`tems or solely human-based social networking. In other
`words, the present invention employs computing systems to
`facilitate navigation through human Social networks for the
`discovery of social opportunities.
`One particular aspect of the invention relies in part upon an
`individuals willingness to truthfully state, but not necessarily
`publish or advertise, personal attributes (e.g., experience,
`occupation, interests, hobbies, historical information, . . . ),
`and other individual(s) that can verify validity of the pub
`lished attributes. For example, a query from an individual
`(e.g., person A) in accordance with one particular aspect of
`the invention identifies a Suitable match of individuals (e.g.,
`people B, C, D) that claim to have specific attributes sought
`after, and at least one other individual (e.g., individual E) that
`can verify existence of the desired attribute. Individual E is
`identified by connections of for example “a friend of a friend’
`that map back to someone that individual A knows and trusts
`in a Social network environment.
`In accordance with another aspect of the Subject invention,
`human Social networks are abstracted into a searchable data
`base populated with information related to individuals that
`make up the respective social networks. A search engine
`receives a query, and an analysis is performed based in part on
`the query, the source (e.g., individual) making the query, and
`information, people and entities related to the query within
`the database. A mapping is performed to determine a desir
`able or optimal path from the individual making the query to
`a person having information related to what is sought after via
`the query. The path can, but is not required to be the shortest
`path from the individual to the person having the information.
`The search engine exposes at least a portion of the path to the
`individual making the query So as to lead the source of the
`query in the proper direction but also maintaining trust integ
`rity associated with the social network. Thus, if there is a node
`(e.g., individual) in the path that does not wish to expose the
`individual making the query to another node in the path for
`any of a number of reasons, the individual making the query
`is prevented from contacting (e.g., being exposed) to the other
`node. Such aspect of the invention has a firewall effect
`wherein respective individuals/friends (e.g., designees) along
`a given path serve as gatekeepers of privacy to individuals/
`friends downstream in the path. Accordingly, a powerful
`human-based trust mechanism is employed in connection
`with modern day computing systems to provide a powerful
`and reliable means for navigation through a human social
`network.
`Thus the subject invention provides for systems and meth
`ods that enable searches of Social networks by acting as a
`“compass” that assists users in navigating a social network.
`Individual user participation is not required in response to
`queries from other users. The systems and methods of the
`Subject invention offer navigational assistance or information
`as opposed to a traditional search which returns requested
`information, thus currently acceptable Social mechanisms for
`arbitrating trust can be exploited. As a result, users do not
`make their personal information publicly searchable, while at
`the same time, they are protected from potential misrepresen
`tations of facts.
`To the accomplishment of the foregoing and related ends,
`certain illustrative aspects of the invention are described
`herein in connection with the following description and the
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 7,472,110 B2
`
`4
`annexed drawings. These aspects are indicative, however, of
`but a few of the various ways in which the principles of the
`invention may be employed and the present invention is
`intended to include all such aspects and their equivalents.
`Other advantages and novel features of the invention may
`become apparent from the following detailed description of
`the invention when considered in conjunction with the draw
`1ngS.
`
`10
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram illustrating a system for utilizing
`Social information according to an aspect of the invention.
`FIG. 2 illustrates a directed graph of a social network
`according to an aspect of the invention.
`FIG. 3 is a block diagram illustrating a system for utilizing
`Social information according to an aspect of the invention.
`FIG. 4 illustrates a pair of users in a social network accord
`ing to another aspect of the invention.
`FIG. 5 illustrates a user's buddy list according to an aspect
`of the invention.
`FIG. 6 is a block diagram illustrating a system for utilizing
`Social information according to an aspect of the invention.
`FIG. 7 illustrates an exemplary interface for entering a
`buddy list according to an aspect of the invention.
`FIG. 8 illustrates an exemplary entry of personal informa
`tion according to an aspect of the invention.
`FIG. 9 illustrates an exemplary directed graph according to
`an aspect of the invention.
`FIG. 10 illustrates an exemplary Subgraph according to an
`aspect of the invention.
`FIG. 11 illustrates connectivity based on corroboration
`information according to an aspect of the invention.
`FIG. 12 is a block diagram illustrating a system for utiliz
`ing Social information according to an aspect of the invention.
`FIG. 13 illustrates a subgraph for a user with a subgraph
`distance of two according to an aspect of the invention.
`FIG. 14 is a diagram of a data packet generated in response
`to a query according to an aspect of the invention.
`FIG. 15 is a flow diagram illustrating a method of modify
`ing a social network according to an aspect of the invention.
`FIG. 16 is a flow diagram illustrating a method for search
`ing a social network according to an aspect of the invention.
`FIG. 17 is a schematic block diagram of an exemplary
`operating environment for a system configured in accordance
`with the present invention.
`FIG. 18 is a schematic block diagram of an exemplary
`communication environment in accordance with the present
`invention.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`The present invention is now described with reference to
`the drawings, wherein like reference numerals are used to
`refer to like elements throughout. In the following descrip
`tion, for purposes of explanation, numerous specific details
`are set forth in order to provide a thorough understanding of
`the present invention. It may be evident, however, that the
`present invention may be practiced without these specific
`details. In other instances, well-known structures and devices
`are shown in block diagram form in order to facilitate describ
`ing the present invention.
`As used in this application, the terms “component' and
`“system are intended to refer to a computer-related entity,
`either hardware, a combination of hardware and software,
`Software, or software in execution. For example, a component
`may be, but is not limited to being, a process running on a
`
`

`

`5
`processor, a processor, an object, an executable, a thread of
`execution, a program, and/or a computer. By way of illustra
`tion, both an application running on a server and the server
`can be a component. One or more components may reside
`within a process and/or thread of execution and a component
`may be localized on one computer and/or distributed between
`two or more computers.
`FIG. 1 schematically illustrates at a high-level a social
`networking system 100 in accordance with the present inven
`tion. The system facilitates maintaining privacy of personal
`information within a database search environment, and also
`can facilitate conducting queries of databases for purposes of
`locating personal attribute information of an unknown per
`son, and allow an originator of a query to evaluate a level of
`trust associated with an individual identified by a query.
`In accordance with the system 100, a query 102 (e.g.,
`natural language based query) is received by a search engine
`104, which processes in part the query 102. For example, the
`query can be natural language based natural language is
`structured so as to matcha user's natural pattern of speech. Of
`course, it is to be appreciated that the Subject invention is
`applicable to many suitable types of querying schemes. The
`search engine 104 includes a parser 106 that parses the query
`into terms germane to the query and employs these terms in
`connection with executing an intelligible search coincident
`with the query 102. The parser 106 can break down the query
`into fundamental indexable elements or atomic pairs, for
`example. An indexing component 108 sorts the atomic pairs
`(e.g., word order and/or location order) and interacts with
`indices 114 of searchable subject matter and terms in order to
`facilitate searching. Additionally, the query 102 generally
`includes a query distance, which defines a distance from an
`originator of the query (e.g., individual, entity) to which the
`search is limited.
`The system 100 further includes a storage 120 that stores a
`variety of data Such as for example, user/entity profiles 124.
`indices 114, and a directed graph 130 of a social network. The
`profiles 124 contain attributes of individuals or entities asso
`ciated with a social network in accordance with the present
`invention. The respective profiles can vary as to quantity as
`well as quality and type of attribute information. In accor
`dance with one aspect of the invention, the profile information
`is directly input via each respective individual or entity. How
`ever, it is to be appreciated that any of a variety of information
`gathering schemes and Sub-Schemes (e.g., data mining, cook
`ies, data scavenging, 3" party providers .
`. . ) could be
`employed in connection with the subject invention if desired.
`The directed graph 130 is a large collection of information
`relating to individuals and relationships between those indi
`viduals. The directed graph 130 although pictorially depicted
`as a graph of Vertices and arcs can take many data-structure
`type forms (e.g., table, relational databases, XML based data
`bases), and functionally represents intra-relationships
`between subsets of individuals and/or entities within the
`social network. The directed graph 130 is discussed in greater
`detail below with respect to FIG. 2.
`The search engine 110 thus receives the query 102 and via
`employment of the parser 106, indexing component 108,
`profiles 124, indices 114 and social network database 130
`determines final node(s) (e.g., individual(s) or entity(s)) hav
`ing information corresponding to the query 102, and also
`determines most efficient paths from the source of the query
`to the final node(s). The search engine 110 employs a map
`ping component 140 in connection with mapping relevant
`paths from the source of the query to the final node(s). The
`search engine 110 also comprises a privacy component 150
`that facilitates determining a degree of exposure of path por
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 7,472,110 B2
`
`10
`
`15
`
`6
`tions to the Source. One particular security implementation
`(e.g., babushka concept) is discussed infra in connection with
`the discussion relating to FIG. 14. The privacy component
`150 can selectively expose and shield data in connection with
`the search in order to maintain privacy and trusts in accor
`dance with the subject invention. For example, there may be
`three nodes (B, C, D) within a path from source A to destina
`tion E; and the privacy component may only expose node B to
`source A as part of a query result. Node B can decide whether
`or not to expose source A to a downstream node (e.g., Node C)
`in the path, and likewise if applicable Node C can perform the
`same sort of exposure analysis with respect to exposing Node
`D. Thus, the privacy component 150 facilitates maintaining
`privacy and trusts associated with respective nodes and intra
`relationships of those nodes.
`It is appreciated that the query 102 can be permitted or
`denied by the system 100. The system 100 can track user
`performance and behavior (e.g., how many queries Submitted
`versus how many answered). Then, based on that behavior,
`the system 100 can decide whether to permit or deny requests
`from that user. By So doing, a degree of fairness can be
`enforced by requiring users to positively contribute and not
`just place numerous queries.
`FIG. 2 illustrates the directed graph 130 of a social network
`according to an aspect of the invention. As noted above, the
`social network database 120 (FIG.1) stores information relat
`ing to social network(s). The directed graph 130 corresponds
`to a subset of at least one of a plurality of the social networks
`that have corresponding information stored in the Social net
`work database 120. The depicted directed graph 130 is sim
`plified for illustrative purposes only and illustrates some typi
`cal relationships between people in a social network. It is
`appreciated that a social network (e.g., embodied as a directed
`graph) employed in accordance with the present invention
`can have any suitable number of Vertices (persons) and arcs
`(relationships). With the graph 130 individuals and/or entities
`inaparticular Social network are represented by Vertices (e.g.,
`nodes), and a relationship between two vertices are repre
`sented via an arc connecting the vertices. The vertices can be
`annotated with information (e.g., attributes) about the indi
`vidual or entity represented by the vertex. It is to be appreci
`ated that two or more arcs can be employed with respect to
`two vertices. More particularly, a unidirectional relationship
`between a first vertex with respect to a second vertex can be
`represented by a first arc, and a unidirectional relationship
`between the second vertex with respect to the first vertex can
`be represented via a second arc. Moreover, it is to be appre
`ciated that additional arcs could be employed wherein respec
`tive arcs can represent unique Subsets corresponding to rela
`tionships.
`With respect to FIG.2, a brief example with respect to logic
`associated with a one particular aspect of a directed graph is
`now described with respect to individual A and individual B
`having a relationship. An arc points from individual A to
`individual B indicating that A is familiar with B (e.g., A
`considers B to be his or her “buddy')—the notion of famil
`iarity is described in detail infra with respect to FIG. 4 and
`thereafter. Because of their relationship, individual A is typi
`cally willing to provide personal information to individual B
`that he/she would not, necessarily, want made public or even
`want others to view. Individuals B, C and D comprise a list or
`buddy list of individual A, implying that A has a personal
`relationship with B, C and D. The relationship of A with
`respect to B, C and D is illustrated by arcs connecting A to B.
`C and D. The directionality of the arcs indicate that A contacts
`B and D for information and is contacted by C for informa
`tion. Individuals C and F are depicted via two arcs as having
`
`

`

`7
`a common pair of relationships, wherein each individual (C
`and F) considers the other a buddy or friend, and is willing to
`contact each other for information and is willing to provide
`information to each other—as noted Supra, this pair of rela
`tionships can also be referred to as a bi-directional relation
`ship. It is to be appreciated that any of a number of suitable
`algorithms, programs and/or relational database schemes to
`effect the functionality associated with the directed graph 130
`can be employed and are intended to fall within the scope of
`the hereto appended claims. It is to be appreciated that indi
`viduals can have respectively differing values (e.g., views)
`with respect to each relationship, and the Subject invention
`contemplates reconciling Such differing values (e.g., to miti
`gate a user from abusing a system employing the invention for
`example via spamming individuals by declaring a familiarity
`therewith). (See infra discussion relating to FIG. 4 and there
`after).
`Turning now to FIG. 3, a specific embodiment of the sub
`ject invention is described in detail. A system 300 that utilizes
`Social information according to an aspect of the invention is
`depicted. The system 300 comprises a set of users 302, a
`private storage component 304 and a search engine 306. The
`system 300 acts as a compass to facilitate guiding users
`toward reliable social information and opportunities whilst
`maintaining privacy of the set of users 302. The system 300
`generates a Social network, maintains the Social network and
`provides navigation information based on the Social network.
`Although, the present invention describes the system 300
`in primarily a monolithic sense, it is to be appreciated that
`after the Social network is populated, the Social network can
`30
`become part of a distributed network wherein individual com
`puting system(s) can maintain and employ the social network.
`Moreover, as the Social network ch