在线社交网络上的修改结构化搜索查询

摘要

在一个实施方式中，方法包括访问包括多个节点和多条矢线的社交图谱，接收包括对选择的节点和矢线的引用的结构化查询，并且生成用于结构化查询的一个或多个查询修改，其中每个查询修改包括对来自多个节点和多条矢线的修改的节点或修改的矢线的引用。

说明书

技术领域

本公开内容总体涉及社交图谱和对社交网络环境中的对象执行搜索。

背景技术

可包括社交网络网站的社交网络系统能够使其用户(诸如，个人或组 织)与其交互并且通过其彼此交互。随着用户输入，社交网络系统可以在 社交网络系统中创建并储存与用户相关联的用户配置文件。用户配置文件 可包括用户的人口统计信息、通信信道信息以及个人兴趣信息。社交网络 系统还可利用来自用户的输入创建并存储用户与社交网络系统中的其他 用户的关系的记录，以及提供便于两个用户或多个用户之间的社交交互的 服务(例如，涂鸦墙(wall post)、照片分享、事件组织、消息、游戏或者 广告)。

社交网络系统可以通过一个或多个网络将与其服务相关的内容或消 息传输至用户的手机或其他计算设备。用户还可以在用户的手机或其他计 算设备上安装软件应用程序，用于访问用户的用户配置文件以及社交网络 系统内的其他数据。社交网络系统可生成一组个性化的内容对象以显示给 用户，诸如，连接到该用户的其他用户的集合的故事的新闻馈送。

社交图谱分析在由节点和矢线构成的网络理论方面显示社交关系。节 点表示网络中的各个行动者，并且矢线表示行动者之间的关系。通常，基 于图谱生成的结构非常复杂。可能存在多种类型的节点和用于连接节点的 多种类型的矢线。就其最简单的形式而言，社交图谱是所研究的所有节点 之间的所有相关矢线的映射图。

发明内容

在具体实施方式中，社交网络系统响应于从用户接收的文本查询可生 成包括对应于识别的社交图谱元素的查询令牌的结构化查询。通过响应于 用户的文本查询而提供建议的结构化查询，社交网络系统可基于其社交图 谱属性及其各个社交图谱元素的关系为在线社交网络中的用户提供搜索 社交图谱中所表示的元素的有力方法。

在具体实施方式中，社交网络系统可从用户接收非结构化文本查询。 作为响应，社交网络系统可访问社交图谱并且然后对文本查询进行解析， 以识别对应于来自文本查询中的n元语法的社交图谱元素。然后，社交网 络系统可访问诸如与上下文无关的语法模型的语法模型。识别的社交图谱 元素可以用作语法模型的语法中的终端令牌(“查询令牌”)。可以选择可 以利用所有识别的查询令牌的任意语法。这些语法可以通过首先生成对应 于文本查询的语义树来识别，然后对语法森林(grammar forest)进行分析 以找到与语义树匹配的子树。选择的语法然后可以用来生成包括对识别的 社交图谱元素的查询令牌的引用的自然语言结构化查询。该结构化查询则 可被传输并显示给用户，其中，用户然后可选择适当的查询以搜索希望的 内容。

在具体实施方式中，响应于结构化查询，社交网络系统可以生成对应 于结构化查询的一个或多个搜索结果。这些搜索结果可以作为搜索结果页 面的部分传输至查询用户。每个搜索结果可包括一个或多个片断，其中片 断可以是关于对应于搜索结果的社交图谱实体的上下文信息。例如，片断 可以是来自与节点相关联的资料页面的信息。每个搜索结果还可以包括提 供用于搜索结果的社交图谱信息的至少一个片断。这些片断可以包含对来 自用于生成搜索结果的结构化查询的查询令牌的引用。

在具体实施方式中，响应于结构化查询，社交网络系统可以生成用于 结构化查询的一个或多个查询修改。每个查询修改可包括对来自社交图谱 的修改的节点或者修改的矢线的引用，可以用于添加或替换结构化查询中 的查询令牌。查询修改可以显示在搜索结果页面上，允许用户观察搜索结 果然后选择一个或多个查询修改以细化或者行转列结构化查询并且生成 新的搜索结果。在利用具体的查询修改修改结构化查询之后，适当的语法 可以用于生成包括对用于查询修改的社交图谱元素的引用的新的自然语 言结构化查询。社交网络系统还可以生成可以显示在搜索结果页面上的替 代的结构化查询。这些替代的结构化查询包括建议的查询、扩大的查询、 和消歧查询。

根据本发明的实施方式被具体公开在涉及方法、存储介质和系统的所 附权利要求中，其中，在一个权利要求类型(例如，方法)中提到的任意 特征也可在另一个权利要求类型(例如，系统)中要求保护。

在根据本发明的实施方式中，方法包括，通过计算设备：

访问包括多个节点和连接节点的多条矢线的社交图谱，两个节点之间 的每条矢线均表示两个节点之间的单一的间隔度，节点包括：

第一节点，对应于与在线社交网络相关联的第一用户；以及

多个第二节点，所述多个第二节点中的每个均对应于概念或者与在线 社交网络相关联的第二用户；

从第一用户接收第一结构化查询，第一结构化查询包括对多个第二节 点中的一个或多个选择的节点和多条矢线中的一条或多条选择的矢线的 引用；以及

生成用于第一结构化查询的一个或多个查询修改，每个查询修改包括 对多个第二节点中的一个或多个修改节点或者多条矢线中的一条或多条 修改矢线的引用。

对修改节点和修改矢线的引用可以是对用于第一结构化查询的额外 的节点或者额外的矢线的引用。

对修改节点和修改矢线的引用可以是对用于第一结构化查询的替代 的节点或者替代的矢线的引用，对替代的节点的每个引用替换对第一结构 化查询的选择的节点的引用，对替代的矢线的每个引用替换对第一结构化 查询的选择的矢线的引用。

在另一实施方式中，方法包括：

确定每个查询修改的得分；以及

将查询修改中得分大于阈值得分的一个或多个查询修改传输至第一 用户。

确定每个查询修改的得分可以基于与第一用户相关联的搜索历史。

确定每个查询修改的得分也可以基于查询修改与第一结构化查询的 社交相关性。

确定每个查询修改的得分可以进一步基于对应于查询修改的可能的 搜索结果的数量。

在又一个实施方式中，方法包括生成对应于第一结构化查询的一个或 多个搜索结果，其中，每个搜索结果对应于多个第二节点中通过选择的矢 线中的至少一个连接到选择的节点中的至少一个的第二节点。

每个搜索结果可以包括一个或多个片断，每个片断包括关于对应于搜 索结果的第二节点的上下文信息。

每个搜索结果可以包括用于第一结构化查询查询修改，第一结构化查 询包括对对应于搜索结果的第二节点的引用。

每个搜索结果可以包括第二结构化查询，第二结构化查询包括对对应 于搜索结果的第二节点的引用。

在又一个实施方式中，方法包括将一个或多个搜索结果传输至第一用 户。

另一实施方式，其中，如果对应于第一查询的一个或多个搜索结果的 数目低于搜索结果的阈值数目，那么该实施方式可以包括：

生成一个或多个第二结构化查询，所述一个或多个第二结构化查询包 括对来自第一结构化查询的零个以上选择的节点和零个以上选择的矢线 的引用，每个第二结构化查询包括与第一结构化查询相比至少少一个的对 所述选择的节点或者所述选择的矢线的引用；以及

将一个或多个第二结构化查询传输至第一用户。

在另一实施方式中，方法包括：

基于第一结构化查询生成一个或多个第二结构化查询；以及

将一个或多个第二结构化查询传输至第一用户。

生成用于第一结构化查询的一个或多个查询修改可以包括：

访问包括多种语法的与上下文无关的语法模型，每种语法均包括一个 或多个查询令牌；

识别一种或多种语法，每个识别的语法具有对应于在第一结构化查询 中引用的所述选择的节点和所述选择的矢线的每个的查询令牌以及至少 一个额外的查询令牌或者替代的查询令牌；以及

生成一个或多个查询修改，所述一个或多个查询修改对应于来自识别 的语法的一个或多个额外的查询令牌或者一个或多个替代的查询令牌。

在又一个实施方式中，方法包括将一个或多个查询修改传输至第一用 户。

在另一实施方式中，方法包括：

从第一用户接收查询修改中的一个或多个的选择；以及

生成第二结构化查询，第二结构化查询包括对所述选择的节点、所述 选择的矢线、和在所选择的查询修改中引用的每个额外的节点或者额外的 矢线的引用。

在本发明的另一实施方式中，还可以请求保护一种或多种实施软件的 计算机可读非易失性存储介质，当执行软件时能操作以：

访问包括多个节点和连接节点的多条矢线的社交图谱，两个节点之间 的每条矢线均表示两个节点之间的单一的间隔度，节点包括：

第一节点，对应于与在线社交网络相关联的第一用户；以及

多个第二节点，所述多个第二节点中的每个均对应于概念或者与在线 社交网络相关联的第二用户；

从第一用户接收包括对多个第二节点中的一个或多个选择的节点和 多条矢线中的一条或多条选择的矢线的引用的第一结构化查询；以及

生成用于第一结构化查询的一个或多个查询修改，每个查询修改包括 对多个第二节点中的一个或多个修改节点或者多条矢线中的一条或多条 修改矢线的引用。

在本发明的另一实施方式中，还可以要求保护，一种系统，包括一种 或多种处理器；和耦接至处理器的内存，内存包括通过能由处理器执行的 指令，处理器在执行指令时能操作以：

访问包括多个节点和连接节点的多条矢线的社交图谱，两个节点之间 的每条矢线均表示两个节点之间的单一的间隔度，节点包括：

第一节点，对应于与在线社交网络相关联的第一用户；以及

多个第二节点，所述多个第二节点中的每个均对应于概念或者与在线 社交网络相关联的第二用户；

从第一用户接收第一结构化查询，第一结构化查询包括对多个第二节 点中的一个或多个选择的节点和多条矢线中的一条或多条选择的矢线的 引用；以及

生成用于第一结构化查询的一个或多个查询修改，每个查询修改包括 对多个第二节点中的一个或多个修改节点或者多条矢线中的一条或多条 修改矢线的引用。

在本发明的另一实施方式中，一种或多种实施软件的计算机可读非易 失性存储介质，当软件被执行时能操作以执行根据本发明或者上述实施方 式的任一个的方法。

在本发明的另一实施方式中，系统包括：一个或多个处理器；和耦接 至处理器的内存，内存包括能由处理器执行的指令，处理器当执行指令时 能操作以执行根据本发明或上述实施方式的任一个的方法。

附图说明

图1示出了与社交网络系统相关联的示例性网络环境。

图2示出了示例性社交图谱。

图3示出了在线社交网络的示例性网页。

图4A至图4B示出了社交网络的示例性查询。

图5A示出了示例性语义树。

图5B示出了示例性语法森林。

图6示出了用于使用与上下文无关的语法模型来生成自然语言结构的 搜索查询的示例性方法。

图7A至图7G示出示例性搜索结果页面。

图8示出用于生成搜索结果和片断的示例性方法。

图9示出用于修改结构搜索查询的示例性方法。

图10示出了示例性计算机系统。

具体实施方式

系统概述

图1示出了与社交网络系统相关联的示例性网络环境100。网络环境 100包括通过网络110连接到彼此的客户端系统130、社交网络系统160 以及第三方系统170。尽管图1示出了客户端系统130、社交网络系统160、 第三方系统170以及网络110的具体布置，然而本公开考虑客户端系统 130、社交网络系统160、第三方系统170以及网络110的任意合适布置。 作为示例而不是限制的方式，客户端系统130、社交网络系统160以及第 三方系统170中的两个或多个可旁通网络110直接彼此连接。作为另一示 例，客户端系统130、社交网络系统160以及第三方系统170中的两个或 多个可物理地或逻辑地整体或部分共同位于同一位置。而且，尽管图1示 出了具体数目的客户端系统130、社交网络系统160、第三方系统170以 及网络110，然而本公开内容也考虑任意合适数目的客户端系统130、社 交网络系统160、第三方系统170以及网络110。作为示例而不是限制的 方式，网络环境100可包括多个客户端系统130、社交网络系统160、第 三方系统170以及网络110。

本公开内容考虑任意合适的网络110。作为示例而不是限制的方式， 网络110的一个或多个部分可包括自组织网络、内联网、外联网、虚拟专 用网络(VPN)、局域网络(LAN)、无线LAN(WLAN)、广域网络(WAN)、 无线WAN(WWAN)、城域网(MAN)、互联网的一部分、公共交换电话 网(PSTN)的一部分、蜂窝电话网络、或者这些的两个或多个的组合。 网络110可包括一个或多个网络110。

链路150可将客户端系统130、社交网络系统160以及第三方系统170 连接到通信网络110或者彼此连接。本公开内容考虑任意合适的链路150。 在具体实施方式中，一个或多个链路150包括一个或多个有线链路(诸如， 数字用户线路(DSL)或电缆数据服务接口规范(DOCSIS))、无线链路 (诸如，Wi-Fi或全球互通微波存取(WiMAX))、或者光链路(诸如，同 步光纤网(SONET)或同步数字系统(SDH))。在具体实施方式中，一个 或多个链路150各自包括自组织网络、内联网、外联网、VPN、LAN、 WLAN、WAN、WWAN、MAN、互联网的一部分、PSTN的一部分、以 蜂窝技术为基础的网络、以卫星通信技术为基础的网络、另一个链路150 或者两个或者多个此类链路150的组合。链路150在整个网络环境100中 不必相同。一个或多个第一链路150可以在一个或多个方面不同于一个或 多个第二链路150。

在具体实施方式中，客户端系统130可以是包括硬件、软件、或者嵌 入的逻辑组件或者两个或者多个这种组件的组合并且能够实施通过客户 端系统130实施或者支持的适当的功能的电子设备。作为实施例而不是限 制性方式，客户端系统130可包括诸如桌面型计算机、笔记本或者膝上型 计算机的计算机系统、上网本、平板电脑、电子书阅读器、GPS设备、照 相机、个人数字助理(PDA)、手持式电子设备、蜂窝电话、智能手机、 其他合适的电子设备或者其任意合适组合。本公开内容考虑了任意合适的 客户端系统130。客户端系统130可以使客户端系统130中的网络用户能 够访问网络110。客户端系统130可以使其用户能够与在其他客户端系统 130中的其他用户通信。

在具体实施方式中，客户端系统130可包括网络浏览器132，诸如， 微软互联网浏览器(MICROSOFT INTERNET EXPLORER)、谷歌浏览器 (GOOGLE CHROME)或火狐浏览器(MOZILLA FIREFOX)，并且可以 具有一个或多个添加件、插件或者其他扩展，诸如，工具栏(TOOL BAR) 或雅虎工具栏(YAHOO TOOL BAR)。客户端系统130中的用户可以进入 将网络浏览器132引导至具体服务器(诸如，服务器162或者与第三方系 统170相关联的服务器)的统一资源定位器(URL)或者其他地址，并且 网络浏览器132可以生成超文本传输协议(HTTP)请求并且将HTTP请 求传送至服务器。服务器可接受HTTP请求并且响应于HTTP请求将一个 或多个超文本令牌语言(HTML)文件传送至客户端系统130。客户端系 统130可以基于来自服务器的HTML文件渲染用于呈现网页给用户。本 公开内容考虑了任意合适的网页文件。作为示例而不是限制的方式，网页 可根据具体需要从HTML文件、可扩展的超文本令牌语言(XHTML)文 件或者可扩展的令牌语言(XML)文件进行渲染。这些网页还可执行脚本 程序，诸如，例如但不限于，以JAVASCRIPT、JAVA、MICROSOFT  SILVERLIGHT，诸如AJAX(异步JAVASCRIPT和XML)等令牌语言 和脚本程序组合编写的程序。本文中，在合适的情况下，对网页的引用包 括一个或多个对应的网页文件(浏览器可以用其渲染网页)，反之亦然。

在具体实施方式中，社交网络系统160可以是可承载在线社交网络的 网络可寻址计算系统。社交网络系统160可生成、存储、接收以及传输社 交网络数据，例如，用户配置文件数据、概念配置文件数据、社交图谱信 息或者与在线社交网络相关的其他合适的数据。社交网络系统160可由网 络环境100的其他组件直接或者经由网络110访问。在具体实施方式中， 社交网络系统160可包括一个或多个服务器162。每个服务器162可以是 单一服务器或者跨越多个计算机或多个数据中心的分布式服务器。服务器 162可以是各种类型，诸如，例如但不限于，网络服务器、新闻服务器、 邮件服务器、消息服务器、广告服务器、文件服务器、应用服务器、交换 服务器、数据库服务器、代理服务器、本文中所描述的适于执行功能或过 程的另一个服务器或者它们的任意组合。在具体实施方式中，每个服务器 162可包括硬件、软件、或嵌入式逻辑组件或者用于执行由服务器162实 施或支持的适当功能的两个或多个该组件的组合。在具体实施方式中，社 交网络系统160可包括一个或多个数据存储器164。数据存储器164可用 于存储各种类型的信息。在具体实施方式中，可根据具体数据结构组织数 据存储器164中存储的信息。在具体实施方式中，每个数据存储器164可 以是相关数据库。具体实施方式可提供能够使客户端系统130、社交网络 系统160或者第三方系统170管理、检索、修改、添加或者删除存储在数 据存储器164中的信息的接口。

在具体实施方式中，社交网络系统160可将一个或多个社交图谱存储 在一个或多个数据存储器164中。在具体实施方式中，社交图谱可包括多 个节点，其可包括多个用户节点(每个用户节点对应于具体用户)或多个 概念节点(每个概念节点对应于具体概念)，以及连接节点的多个矢线。 社交网络系统160可向在线社交网络的用户提供与其他用户通信和交互的 能力。在具体实施方式中，用户可经由社交网络系统160加入在线社交网 络，且然后添加社交网络系统160中用户希望与其连接的多个其他用户的 连接(即，关系)。本文中，术语“好友”可能指的是用户经由社交网络 系统160与其形成连接、关联或者关系的社交网络系统160的任意其他用 户。

在具体实施方式中，社交网络系统160可向用户提供对社交网络系统 160支持的各种类型的项目或对象采取行动的能力。作为示例而不是限制 的方式，项目和对象可包括社交网络系统160的用户可能属于的群体或者 社交网络、用户可能感兴趣的事件或日历条目、用户可以使用的以计算机 为基础的应用程序、允许用户经由服务购买或出售项目的交易、用户可以 执行的与广告的交互、或者其他合适的项目或对象。用户可与能够在社交 网络系统160中或者通过第三方系统170的外部系统表示的、独立于社交 网络系统160并且经由网络110耦接至社交网络系统160的任意事物交互。

在具体实施方式中，社交网络系统160可以能够连接各种实体。作为 示例而不是限制的方式，社交网络系统160可以能够使用户彼此交互，以 及从第三方系统170或者其他实体接收内容，或者允许用户通过应用编程 接口(API)或者其他通信信道与这些实体交互。

在具体实施方式中，第三方系统170可包括一种或者多种类型的服务 器、一个或者多个数据存储器、一个或者多个接口，其中包括但不限于 API、一个或者多个网络服务、一种或者多种内容来源、一个或者多个网 络或者(例如，服务器可与其通信的)任意其他合适组件。可以由不同于 操作社交网络系统160的实体的实体来操作第三方系统170。然而，在具 体实施方式中，社交网络系统160和第三方系统170可以彼此结合进行操 作以将社交网络服务提供给社交网络系统160或者第三方系统170的用 户。在这种意义上，社交网络系统160可以提供平台或者主干网，诸如第 三方系统170的其他系统，可用于通过互联网将社交网络服务和功能提供 给用户。

在具体实施方式中，第三方系统170可包括第三方内容对象提供商。 第三方内容对象提供商可包括内容对象的一个或多个来源，其可以被传送 至客户端系统130。作为示例而不是限制的方式，内容对象可包括用户感 兴趣的关于事物或活动的信息，诸如，电影放映次数、电影评论、餐馆评 论、餐馆菜单、产品信息和评论、或其他合适的信息。作为另一个实例并 非限制性方式，内容对象可包括激励性内容对象，诸如，优惠券、打折票、 礼品券、或者其他合适的激励对象。

在具体实施方式中，社交网络系统160还包括用户生成的内容对象， 其可以提高用户与社交网络系统160的交互。用户生成的内容可包括用户 可添加、上传、发送、或者“发帖(post)”到社交网络系统160的任意事。 作为示例而不是限制的方式，用户将帖子从客户端系统130传送至社交网 络系统160。帖子可包括诸如状态更新或者其他文本数据、位置信息、照 片、视频、链接、音乐或者其他类似数据或媒体的数据。第三方还可通过 诸如新闻馈送或者流等“通信信道”将内容添加到社交网络系统160中。

在具体实施方式中，社交网络系统160可包括各种服务器、子系统、 程序、模块、日志以及数据存储器。在具体实施方式中，社交网络系统160 可包括以下一种或多种：网络服务器、动作记录器、API请求服务器、相 关性和排列发动机、内容对象分类器、通知控制器、动作日志、第三方内 容对象曝光日志、推断模块、授权/隐私服务器、检索模块、广告目标模块、 用户接口模块、用户配置文件存储器、连接存储器、第三方内容存储器、 或者位置存储器。社交网络系统160还可包括诸如网络接口的合适的组件、 安全机构、负载均衡器、故障转移服务器、管理和网络操作控制台、其他 合适的组件、或其任意合适的组合。在具体实施方式中，社交网络系统160 可包括存储用户配置文件的一个或多个用户配置文件存储器。例如，用户 配置文件可包括传记信息、人口统计信息、行为信息、社交信息或者其他 类型的描述性信息，诸如，工作经历、教育背景、业余爱好或者偏好、兴 趣、亲和性或者位置。兴趣信息可包括与一个或多个种类相关的兴趣。种 类可以是总体的或者具体的。作为示例而不是限制的方式，如果用户“喜 欢”关于一个品牌鞋子的物品，该种类可以是该品牌、或者“鞋子”或“衣 物”的总体种类。连接存储器可用于存储关于用户的连接信息。连接信息 可显示具有相似或者共同工作经历、群体成员关系、业余爱好、教育背景、 或者以任意方式与共同属性有关或者享有共同属性的用户。连接信息还可 包括不同用户与内容(内部内容和外部内容两种)之间的用户定义的连接。 网络服务器可以用于将社交网络系统160经由网络110连接到一个或多个 客户端系统130或者一个或多个第三方系统170。网络服务器可包括用于 接收和路由社交网络系统160与一个或多个客户端系统130之间的消息的 邮件服务器或者其他消息功能。API请求服务器可以允许第三方系统170 通过呼叫一个或多个API来访问来自社交网络系统160的信息。动作记录 器可以用于接收来自网络服务器的关于用户在社交网络系统160之上或之 外的行动的信息。结合动作日志，可以保存用户暴露给第三方内容对象的 第三方内容对象日志。通知控制器可以将关于内容对象的信息提供给客户 端系统130。信息可作为通知推送至客户端系统130，或者响应于从客户 端系统130接收的请求，可以从客户端系统130拖曳信息。授权服务器可 用于执行社交网络系统160的用户的一个或多个隐私设置。用户的隐私设 置确定如何分享与用户相关联的具体信息。授权服务器可以允许用户决定 是否允许由社交网络系统160记录其活动，或者诸如通过设置合适的隐私 设置与其他系统(例如，第三方系统170)共享其活动。第三方内容对象 存储器可用于存储从第三方接收的内容对象，诸如，第三方系统170。位 置储存器可用于存储从与用户相关联的客户端系统130接收的位置信息。 广告定价模块将社交信息、当前时间、位置信息或者其他合适的信息进行 组合，从而以通知的形式将相关广告提供给用户。

社交图谱

图2示出示例性社交图谱200。在具体实施方式中，社交网络系统160 可将一个或多个社交图谱200存储在一个或多个数据存储器中。在具体实 施方式中，社交图谱200可包括多个节点-其可包括多个用户节点202或 多个概念节点204-以及连接节点的多个矢线206。出于教导之目的，以二 维可视图表示法示出了图2中所示的示例性社交图谱200。在具体实施方 式中，社交网络系统160、客户端系统130或者第三方系统170可访问社 交图谱200以及用于合适应用的相关社交图谱信息。例如，社交图谱200 的节点和矢线可作为数据对象存储在数据存储器(诸如，社交图谱数据库) 中。这种数据存储器可包括社交图谱200的节点或矢线的一个或多个可查 找的或者可搜寻的索引。

在具体实施方式中，用户节点202可对应于社交网络系统160的用户。 作为示例而不是限制的方式，用户可以是与或通过社交网络系统160交互 或者通信的个体(人类用户)、实体(例如，企业、商家或第三方应用) 或者(例如，个体的或者实体的)组。在具体实施方式中，当用户在社交 网络系统160中注册账户时，社交网络系统160可创建对应于该用户的用 户节点202，并且将用户节点202存储在一个或多个数据存储器中。在适 当情况下，本文中所描述的用户和用户节点202可指代注册用户和与注册 用户相关联的用户节点202。另外或者可替代地，此处所描述的用户和用 户节点202可，在适当情况下，指代未注册至社交网络系统160的用户。 在具体实施方式中，用户节点202可与通过用户提供的信息或者通过各种 系统(包括社交网络系统160)收集的信息相关联。作为示例而不是限制 的方式，用户可以提供他或她的名字、资料图片、联系信息、生日、性别、 婚姻状况、家庭状况、工作情况、教育背景、偏好、兴趣或其他人口统计 信息。在具体实施方式中，用户节点202可与对应于与用户相关联的信息 的一个或多个数据对象相关联。在具体实施方式中，用户节点202可对应 于一个或多个网页。

在具体实施方式中，概念节点204可对应于概念。作为示例而不是限 制的方式，概念可对应于地点(诸如，电影院、餐馆、地标或城市)；网 站(诸如，与社交网络系统160相关联的网站或者与网络应用服务器相关 联的第三方网站)；实体(诸如，个人、公司、群体、运动队或名人)；可 以位于社交网络系统160中或外部服务器(诸如，网络应用服务器)上的 资源(诸如，音频文件、视频文件、数码照片、文本文件、结构化文档或 应用程序)；不动产或知识产权(诸如，雕塑、绘画、电影、游戏、歌曲、 想法、照片或书面著作)；游戏；活动；想法或理论；另一个合适的概念； 或者这种概念的两个或多个。概念节点204可以与用户提供的概念信息或 者通过各种系统(包括社交网络系统160)收集的信息相关联。作为示例 而不是限制的方式，概念信息可包括名称或标题、一个或多个图像(例如， 书籍的封面图像)；位置(例如，地址或地理位置)；网站(可与URL相 关联)；联系信息(例如，电话号码或电子邮件地址)；其他合适的概念信 息；或者这种信息的任意合适的组合。在具体实施方式中，概念节点204 可以与对应于与概念节点204相关联的信息的一个或多个数据对象相关 联。在具体实施方式中，概念节点204可对应于一个或多个网页。

在具体实施方式中，社交图谱200中的节点可以表示网页(其可被称 为“配置文件页面”)或者由网页表示。配置文件页面可以由社交网络系 统160承载或者可访问社交网络系统160。配置文件页面还可以在与第三 方服务器170相关联的第三方网站上承载。作为示例而不是限制的方式， 对应于具体的外部网页的配置文件页面可以是具体的外部网页，并且配置 文件页面可以对应于具体的概念节点204。配置文件页面可以是所有人或 者其他用户的选择子集可见的。作为示例而不是限制的方式，用户节点202 可具有对应的用户配置文件页面，其中，对应的用户可以添加内容，做出 声明或者他或她自己的其他表达。作为另一个示例并非限制的方式，概念 节点204可具有对应的概念配置文件页面，其中，一个或多个用户可添加 内容，做出声明或者表达他们的想法，具体地，涉及对应于概念节点204 的概念。

在具体实施方式中，概念节点204可以表示第三方网页或者由第三方 系统170承载的资源。第三方网页或资源可包括，在其他元素、内容、可 选择的或其他图标、或者表示动作或活动的其他中间能实行的对象(例如， 其可以在JavaScript、AJAX或PHP编码中执行)中。作为示例而不是限 制的方式，第三方网页可包括可选择的图标，诸如，“喜欢”、“签到”、 “吃”、“推荐”或者另一个合适的动作或活动。观看第三方网页的用户可 能通过选择图标之一(例如，“吃”)执行动作，使客户端系统130向社交 网络系统160传输表示用户的行为的消息。响应于该消息，社交网络系统 160可在对应于用户的用户节点202与对应于第三方网页或资源的概念节 点204之间创建矢线(例如，“吃”矢线)并且在一个或多个数据存储中 存储矢线206。

在具体实施方式中，社交图谱200中的一对节点可以通过一条或多条 矢线206彼此连接。连接一对节点的矢线206可以表示该对节点之间的关 系。在具体实施方式中，矢线206可包括或表示一个或多个数据对象或者 对应于一对节点之间的关系的属性。作为示例而不是限制的方式，第一用 户可以表示第二用户是第一用户的“好友”。响应于该表示，社交网络系 统160可以将“好友请求”传输至第二用户。如果第二用户确认该“好友 请求”，则社交网络系统160可以在社交图谱200中创建将第一用户的用 户节点202连接到第二用户的用户节点202的矢线206，并且在一个或多 个数据存储器24中存储矢线206作为社交图谱信息。在图2的示例中， 社交图谱200包括指示用户“A”与用户“B”的用户节点202之间的好 友关系的矢线206，以及指示用户“C”与用户“B”的用户节点202之间 的好友关系的矢线。尽管本公开内容描述或示出了具有连接具体用户节点 202的具体属性的具体矢线206，但是本公开内容考虑具有连接用户节点 202的任意合适属性的任意合适的矢线206。作为示例而不是限制的方式， 矢线206可以表示友谊、亲属关系、公司或工作关系、爱好者关系、粉丝 关系、访客关系、客户关系、上级/下属关系、相互关系、非相互关系、另 一合适类型的关系或者两种或多种此类关系。此外，尽管本公开内容总体 将节点描述为被连接的，但是本公开内容还将用户或概念描述为被连接 的。在本文中，在适当情况下，对连接的用户或概念的引用可以指代对应 于通过一条或多条矢线206在社交图谱200中被连接的这些用户或概念的 节点。

在具体实施方式中，用户节点202与概念节点204之间的矢线206可 以表示由与用户节点202相关联的用户向与概念节点204相关联的概念执 行的具体动作或活动。作为实例但而不是限制性方式，如图2所示，用户 可“喜欢”、“参与”、“播放”、“收听”、“烹饪”、“就职于”或者“观看” 概念，其中每个均对应于矢线类型或者子类型。例如，对应于概念节点204 的概念配置文件页面可包括可选择的“签到”图标(诸如，可点击的“签 到”图标)或者可选择的“添加到收藏夹”图标。类似地，在用户点击这 些图标之后，响应于对应于各自动作的用户的动作，社交网络系统160可 以创建“收藏夹”矢线或“签到”矢线。作为另一个实例并非限制性方式， 用户(用户“C”)可以使用具体的应用程序(SPOTIFY，它是在线音乐应 用程序)收听具体的歌曲(“Imagine”)。在这种情况下，社交网络系统160 可在对应于用户的用户节点202与对应于歌曲的概念节点204之间创建 “收听”矢线206并且在对应于用户的用户节点202与对应于应用的概念 节点204之间创建“使用”矢线(如图2所示)，以指示用户收听该歌曲 并且使用该应用。而且，社交网络系统160可在对应于歌曲与应用的概念 节点204之间创建“播放”矢线206(如图2所示)，以指示通过该具体应 用播放该具体歌曲。在这种情况下，“播放了”矢线206对应于在外部音 频文件(歌曲“Imagine”)上通过外部应用程序(SPOTIFY)执行的动作。 尽管本公开内容描述了具有连接用户节点202与概念节点204的具体属性 的具体矢线206，但是本公开内容考虑具有连接用户节点202和概念节点 204的任意合适属性的任意合适的矢线206。而且，尽管本公开内容描述 了表示单一关系的用户节点202与概念节点204之间的矢线，但是本公开 内容考虑表现用户节点202与概念节点204之间的一种或多种关系的矢 线。作为示例而不是限制的方式，矢线206可以表示用户喜欢并且以具体 的概念使用了矢线206。可替代地，另一矢线206可表示用户节点202与 概念节点204之间(如图2所示，用户“E”的用户节点202与“SPOTIFY” 的概念节点204之间)的各种类型的关系(或者多种单一关系)。

在具体实施方式中，社交网络系统160可以在社交图谱200中的用户 节点202与概念节点204之间创建矢线206。作为示例而不是限制的方式， 观看概念配置文件页面(诸如，例如通过使用网络浏览器或者用户的客户 端系统130承载的专用应用程序)的用户通过单击或者选择“喜欢”图标 可以表示他或她喜欢通过概念节点204表示的概念，这可以引起用户的客 户端系统130向社交网络系统160传输表示用户对与概念配置文件页面相 关联的概念的喜欢的消息。响应于该消息，社交网络系统160可以在与用 户相关联的用户节点202与概念节点204之间创建矢线206，如通过用户 与概念节点204之间的“喜欢”矢线206所示出的。在具体实施方式中， 社交网络系统160可将矢线206存储在一个或多个数据存储器中。在具体 实施方式中，响应于具体的用户动作，矢线206可以自动地由社交网络系 统160形成。作为示例而不是限制的方式，如果第一用户上传图片，观看 电影或者收听歌曲，则矢线206可在对应于第一用户的用户节点202与对 应于这些概念的概念节点204之间形成。尽管本公开内容描述了以具体的 方式形成具体矢线206，但是本公开内容考虑以任意合适的方式形成任意 合适的矢线206。

广告

在具体实施方式中，广告可以是文本(可以是HTML连接)、一个或 多个图像(可以是HTML连接)、一个或多个视频、音频、一个或多个 ADOBEFLASH文件、这些的合适的组合，或者以在一个或多个网页上、 一个或多个邮件中、或者关于用户请求的搜索结果上呈现的任意合适的数 字格式的任意其他合适的广告。另外或者作为替代，广告可以是一个或多 个被赞助的故事(例如，社交网络系统160上的新闻馈送或者便签(ticker) 项目)。被赞助的故事可以是广告商例如通过使社交动作呈现在用户的配 置文件页面或其他页面的预定区域内、呈现具有与广告商相关联的附加信 息、在新闻馈送或者其他用户的便签内突出或高亮来宣传、或以其它方式 被宣传的用户的社交动作(诸如“喜欢”页面、“喜欢”或者评论页面上 的帖子，RSVP与页面相关联的事件，对页面上张贴的问题进行投票，检 查地点，使用应用程序或者玩游戏，或者“喜欢”或者分享网址)。广告 商可以付费以使社交的动作得到宣传。

在具体实施方式中，可以请求广告用于显示在社交网络系统网页、第 三方网页、或者其余各页内。广告可以显示在页面的专用部分中，诸如在 页面的顶上的横幅区域中、在页面的侧面的纵列中、在页面的GUI中、在 弹出式窗口中、在下拉菜单中、在页面的输入栏中、在页面的内容的顶上、 或者关于页面的别处。另外或者作为替代，可以在应用程序内显示广告。 广告可以显示在专用页面内，在用户可以访问页面或者利用应用程序之 前，要求用户与广告交互或者观看广告。例如，用户可以通过网络浏览器 观看广告。

用户可以任意合适的方式与广告交互。用户可以点击或选择广告。通 过选择广告，用户可以被引导至与广告相关联的页面(或者用户使用的浏 览器或者其他应用程序)。在与广告相关联的页面，用户可以采取另外的 动作，诸如购买与广告相关联的产品或服务，接收与广告相关联的信息， 或者订阅与广告相关联的时事通讯。具有音频或者视频的广告可以通过选 择广告的组件(类似“播放按钮”)来播放。替代地，通过选择广告，社 交网络系统160可以执行或者修改用户的具体的动作。作为示例而不是限 制的方式，广告可以包括在搜索结果页面的搜索结果当中，其中赞助的内 容通过非赞助的内容得到宣传。作为另一示例而不是限制的方式，广告可 以包括在提出的搜索查询当中，其中，引用广告商或者其内容/产品的建议 的查询可以通过非赞助查询宣传。

广告可包括用户可以与其交互的社交网络系统功能。例如，广告可以 允许用户通过选择与认可相关联的图标或者链接来“喜欢”或认可广告。 作为另一示例，广告可以允许用户搜索(例如，通过执行查询)与广告商 相关的内容。类似地，用户可以与另一用户(例如，通过社交网络系统160) 分享广告或者回复(例如，通过社交网络系统160)与广告相关联的事件。 另外或者替代地，广告可包括针对用户的社交网络系统背景。例如，广告 可以显示关于用户在社交网络系统160内的采取与广告的主题相关联的动 作的好友的信息。

预键入过程

在具体实施方式中，一个或多个客户端侧和/或后端(服务器侧)过程 可以实现并且利用“预键入”特征，“预键入”特征可以自动尝试使社交 图谱元素(例如，用户节点202、概念节点204、或者矢线206)与用户当 前正在与请求的可以通过社交网络系统160承载或者在社交网络系统160 中可访问的网页(诸如，用户配置文件页面、概念配置文件页面、搜索结 果网页、或者在线社交网络的另一合适的页面)结合渲染的输入表格中输 入的信息相匹配。在具体实施方式中，当用户输入文本以发布声明时，预 键入特征可以尝试使在声明中输入的文本字符串与对应于社交图谱200中 的用户、概念、或者矢线和它们的对应元素的字符串(例如，名称、描述) 相匹配。在具体实施方式中，当发现匹配时，预键入特征可利用对现有社 交图谱元素的社交图谱元素的引用(诸如，例如节点名称/类型、节点ID、 矢线名称/类型、矢线ID或者另一合适的引用或者标识符)来自动填充该 表格。

在具体实施方式中，当用户将文本键入或输入到用于在用户的配置文 件页面、主页、或者其他页面的不同部分添加内容或者发布声明的表格时， 预键入过程可以与在社交网络系统160(或者内)(例如，服务器162内) 执行的一个或多个前端(客户端侧)和/或后端(服务器侧)预键入过程(在 下文中仅称为“预键入过程”)协力工作，以交互地并且几乎瞬时(如向 用户显现)尝试利用确定是当用户输入文本的字符时与用户输入的文本字 符最相关的或者最匹配的术语或者对应于现有的社交图谱元素的名称的 术语，或者与现有的社交图谱元素相关联的术语自动填充表格。利用社交 图谱数据库中的社交图谱信息或者从社交图谱数据库提取并索引的信息， 包括与节点和矢线相关联的信息，预键入过程，结合来自社交图谱数据库 的信息，以及潜在结合各种其它过程、应用程序、或者位于社交网络系统 160内或者在社交网络系统160内执行的数据库，也许能高精确度地预测 用户的预期的声明。然而，社交网络系统160还可以使用户基本上自由输 入其希望的任意声明，能够使用户自由地表达其自身。

在具体实施方式中，当用户将文本字符输入到表框或者其他字段中 时，预键入过程可尝试识别与用户输入字符时在用户声明中输入的字符串 匹配的现有社交图谱元素(例如，用户节点202、概念节点204或者矢线 206)。在具体实施方式中，当用户将字符输入到表框中时，预键入过程可 读取所输入文本字符的字串。当执行每个按键时，前端预键入过程可将输 入的字符串作为请求(或者呼叫)传输给在社交网络系统160内执行的后 端预键入过程。在具体实施方式中，预键入过程可经由AJAX(异步 JavaScript和XML)或者其他合适技术(具体地，异步技术)通信。在具 体实施方式中，该请求可以是或者包括能够快速或者动态发送或者获取结 果的XMLHTTP请求(XHR)。在具体实施方式中，预键入过程还可以在 请求之前、之后或者与请求一起传输识别其中用户发布声明的具体页面的 具体部分的部分标识符(部分ID)。在具体实施方式中，还可传输用户ID 参数，但是在一些实施方式中，由于用户已被“告知”用户已登录到社交 网络系统160(或通过社交网络系统160认证)，所以不需要发送用户ID 参数。

在具体实施方式中，预键入过程可使用一种或者多种匹配算法来尝试 识别匹配的社交图谱元素。在具体实施方式中，当发现一个或者多个匹配 时，预键入过程可(可利用AJAX或者其他合适的技术)向用户的客户端 系统130传输响应，例如，其中可包括匹配社交图谱元素的名称(名称字 串)或者描述以及潜在地与匹配社交图谱元素相关联的其他元数据。作为 示例而不是限制的方式，如果用户输入字符“pok”到查询字段，预键入 过程可以显示下拉菜单，下拉菜单显示匹配的现有的配置文件页面的名称 和相应的用户节点202或者概念节点204，诸如命名为或者专用于“poker” 或者“pokemon”的配置文件页面，用户然后可以单击或选择从而确认声 明匹配的用户或者对应于所述选择的节点的概念名称的期望。作为另一实 施例而不是限制性方式，一旦单击“poker”，则预键入过程可使用声明 “poker”自动填充或者使网络浏览器132自动填充查询字段。在具体实施 方式中，预键入过程可仅使用匹配排列靠前的名称或者其他标识符自动填 充该字段，而非显示下拉菜单。然后，用户仅通过键入其键盘上的“回车” 键或者通过单击自动填充声明而确认自动填充声明。

在于2010年4月19日提交的美国专利申请第12/763162号和于2012 年7月23日提交的美国专利申请第13/556072号中可以找到关于预键入过 程的更多信息，将其通过引用结合在此。

结构化搜索查询

图3示出了在线社交网络的示例性网页。在具体实施方式中，用户可 通过将文本输入到查询字段350中将查询提交至社交网络系统160。在线 社交网络的用户可通过将描述主题的短语提供至搜索引擎而搜索与具体 主题(例如，用户、概念、外部内容或者资源)有关的信息，通常被称之 为“搜索查询”。查询可以是非结构化文本查询并且可包括一个或多个文 本字串(可包括一种或多种n元语法)。总之，用户可将任意字符串输入 到查询字段350中，以搜索社交网络系统160中与文本查询匹配的内容。 社交网络系统160则可搜索数据存储器164(或者具体地，社交图谱数据 库)，以识别与查询匹配的内容。搜索引擎可基于查询短语使用各种搜索 算法进行搜索并且生成识别与搜索查询最为可能相关的资源或者内容(例 如，用户配置文件页面、内容配置文件页面、或者外部资源)的搜索结果。 为了进行搜索，用户可将搜索查询输入或者传输至搜索引擎。作为响应， 搜索引擎可识别可能与搜索查询有关的一种或者多种资源，该一种或者多 种资源的每种可被单独称为“搜索结果”或者统称为对应于搜索查询的“搜 索结果”。例如，识别内容可包括社交图谱元素(即，用户节点202、概念 节点204、矢线206)、资料页面、外部网页、或者其任意组合。然后，社 交网络系统160可利用对应于识别的内容的搜索结果生成搜索结果网页并 且向用户传输搜索结果网页。搜索结果通常以搜索结果网页上的链接列表 形式向用户呈现，每个链接均与包含一些识别资源或者内容的不同网页相 关联。在具体实施方式中，搜索结果中的每个链接均可以为统一资源定位 符(URL)形式，该统一资源定位符指定了对应网页所在的位置和用于对 其进行检索的机制。然后，社交网络系统160可将搜索结果网页传输至用 户的客户端系统130上的网络浏览器132。用户则可单击URL链接或者从 搜索结果网页中选择内容，以访问来自社交网络系统160或者外部系统(诸 如，第三方系统170)的内容，视情况而定。可根据资源与搜索查询的相 对关联度排列资源并且呈现给用户。还可根据搜索结果与用户的相对关联 度排列搜索结果并且呈现给用户。换言之，例如，可以基于社交图谱信息、 用户信息、用户的搜索或者浏览历史或者与用户有关的其他合适信息使查 询用户的搜索结果个性化。在具体实施方式中，通过由搜索引擎实现的排 列算法可确定资源排列。作为示例而不是限制的方式，与搜索查询或者用 户较为相关的资源可以比与搜索查询或者用户较不相关的资源排列得更 靠前。在具体实施方式中，搜索引擎可使其搜索局限于在线社交网络上的 资源和内容。然而，在具体实施方式中，搜索引擎还可搜索诸如第三方系 统170、互联网或者万维网、或者其他合适来源的其他来源上的资源或者 内容。尽管本公开内容描述了以具体方式查询社交网络系统160，然而本 公开内容考虑以任意合适方式查询社交网络系统160。

在具体实施方式中，此处所描述的预键入过程可适用于由用户输入的 搜索查询。作为示例而不是限制的方式，当用户将文本字符输入到搜索字 段中时，预键入过程可尝试识别在用户输入字符时与输入搜索字段的字符 串匹配的一个或者多个用户节点202、概念节点204或者矢线206。当预 键入过程从文本查询接收包括字串或者n元语法的请求或者呼叫时，预键 入过程可执行或者使执行搜索，以识别具有与输入文本匹配的相应名称、 类型、类别或者其他标识符的现有社交图谱元素(即，用户节点202、概 念节点204、矢线206)。预键入过程可使用一种或者多种匹配算法尝试识 别匹配的节点或者矢线。当发现一个或者多个匹配时，预键入过程可向用 户的客户端系统130传输响应，例如，其中可包括匹配节点的名称(名称 字串)以及潜在地与匹配节点相关联的其他元数据。预键入过程然后可以 显示下拉菜单300，下拉菜单300显示匹配的现有的资料页面的名称和相 应的用户节点202或者概念节点204，并且显示可以连接到匹配的用户节 点202或者概念节点204的匹配的矢线206的名称，用户然后可以单击或 选择从而确认搜索对应于所述选择的节点的匹配的用户或者概念名称，或 者搜索用户或者通过匹配的矢线连接到匹配的用户或者概念的概念的期 望。替代地，预键入过程可简单使用排列在首位的匹配的名称或者其他标 识符来自动填充该表格，而非显示下拉菜单300。然后，用户可仅通过键 盘上的按键“回车”或者通过单击自动填充声明来确认自动填充声明。一 旦用户确认了匹配节点和矢线，预键入过程则可传输请求，以将用户对包 含匹配社交图谱元素的查询的确认通知给社交网络系统160。社交网络系 统160可响应于传输的请求自动(或者替代地，基于请求中的指令)呼叫 或者以其他方式搜索社交图谱数据库，以获得匹配的社交图谱元素或者连 接到匹配社交图谱元素的社交图谱元素，视情况而定。尽管本公开内容描 述了以具体方式将预键入过程应用于搜索查询，然而本公开内容考虑以任 意合适方式将预键入过程应用于搜索查询。

关于搜索查询和搜索结果，具体实施方式可以利用通过引用结合于此 的在于2006年8月11日提交的美国专利申请No.11/503093，2010年12 月22日提交的美国专利申请No.12/977027，和2010年12月23日提交的 美国专利申请No.12/978265中公开的一个或多个系统、组件、元素、功能、 方法、操作、或者步骤。

结构化搜索查询的自然语言渲染

图4A至图4B示出了社交网络的示例性查询。在具体实施方式中， 响应于从第一用户(即，查询用户)接收的文本查询，社交网络系统160 可以生成一个或多个以自然语言语法渲染的结构化查询，其中每个结构化 查询包括与一个或多个识别的社交图谱元素对应的查询令牌。图4A至图 4B示出了查询字段350中的各种示例性文本查询和由此在下拉菜单300 中生成的各种结构化查询。通过响应于用户的文本查询提供建议的结构化 查询，社交网络系统160可基于其社交图谱属性和其与各种社交图谱元素 的关系提供使在线社交网络中的用户搜索社交图谱200中所表示的元素的 有力方式。结构化查询可允许查询用户搜索社交图谱200中通过具体矢线 类型连接到具体用户或者概念的内容。作为示例而不是限制的方式，社交 网络系统160可从第一用户接收非结构化文本查询。作为响应，社交网络 系统160(例如，经由服务器侧元素检测过程)可以访问社交图谱200并 且然后解析文本查询以识别对应于来自文本查询的n元语法的社交图谱元 素。社交网络系统160则可访问诸如与上下文无关的语法模型的包括多个 语法的语法模型。这些语法可以被形象化为组织作为具有多个非终端和终 端令牌的有序树的语法森林。识别的社交图谱元素可以用作语法中的终端 令牌(“查询令牌”)。一旦这些终端令牌已被识别(例如，通过使用对应 于来自用户的文本查询的语义树)，社交网络系统160可以遍历语法森林 来识别相交的非终端节点。然后可以选择通过这些相交的非终端节点之一 表示的各个语法。所选择的语法然后可以用来生成包括引用识别的社交图 谱元素的查询令牌的一项或多项结构化查询。这些结构化查询可基于通过 语法生成的字串，使得使用自然语言句法引用适当的社交图谱元素对它们 进行渲染。结构化查询可被传输至第一用户并且(例如，经由客户端侧预 键入过程)显示在下拉菜单300中，其中，第一用户则可选择搜索希望内 容的适当查询。使用此处所描述的结构化查询的一些优点包括基于有限信 息查找在线社交网络的用户，从而基于该内容与各个社交图谱元素的关系 将在线社交网络中的内容的虚拟索引桥接在一起，或者找出与您和/或您朋 友有关的内容。通过使用该过程，可以对自然语言渲染过程的输出进行有 效解析，例如，生成修改的或者替代的结构化查询。此外，因为该过程使 用的规则来源于语法模型，所以语法模型的规则的任意修改可以直接反映 在渲染过程中。尽管本公开内容描述了并且图4A和图4B示出了以具体 方式生成具体结构化查询，然而本公开内容考虑以任意合适方式生成任意 合适的结构化查询。

在具体实施方式中，社交网络系统160可从查询/第一用户(对应于第 一用户节点202)接收非结构化文本查询。作为示例而不是限制的方式， 第一用户可能希望搜索其他用户，即(1)第一用户的第一重要程度的朋 友；以及(2)与斯坦福大学相关联(即，用户节点202通过矢线206连 接到对应于学校“斯坦福(Stanford)”的概念节点204)。然后，如图4A 和图4B所示，第一用户可以将文本查询“朋友斯坦福(friend stanford)” 输入到查询字段350中。如下拉菜单300中所示，当第一用户将文本查询 输入到查询字段350中时，社交网络系统160可提供各种建议的结构化查 询。如此处使用的，非结构化文本查询是指由用户输入的简单文本字串。 当然，可以根据标准语言/语法规则(例如，英语语法)构造文本查询。然 而，通常将针对社交图谱元素非结构化文本查询。换言之，简单的文本查 询通常不包括对具体社交图谱元素的嵌入式引用。因此，如此处使用的， 结构化查询是指包含对具体社交图谱元素的引用的查询，从而允许搜索引 擎基于所识别元素进行搜索。此外，文本查询可以针对正式的查询句法非 结构化。换言之，简单的文本查询不必要以通过搜索引擎直接可执行的查 询指令的形式。尽管本公开内容描述了以具体方式接收具体查询，然而本 公开内容考虑以任意合适方式接收任意合适查询。

在具体实施方式中，社交网络系统160可对从第一用户(即，查询用 户)接收的非结构化文本查询(也被简称为搜索查询)进行解析，以识别 一种或者多种n元语法。总之，n元语法是给定文本或者语音序列中的n 项的连续序列。项可以是文本或者语音的序列中的字符、音素、音节、字 母、词、基础对、前缀或者其他可识别的项。n元语法可包括由查询用户 输入的文本中的一个或者多个字符(字母、数字、标点等)。大小为一的n 元语法可被称之为“一元语法”，大小为二的n元语法可被称之为“二元 语法”或者“双元语法”，大小为三的n元语法可被称之为“三元语法” 等。每种n元语法均可包括从查询用户接收的文本查询中的一个或者多个 部分。在具体实施方式中，每种n元语法均可包括由第一用户输入的字符 串(例如，文本中的一个或者多个字符)。作为示例而不是限制的方式， 社交网络系统160可对文本查询“朋友斯坦福(friend stanford)”进行解 析，以识别下列n元语法：朋友(friend)；斯坦福(stanford)；朋友斯坦 福(friend stanford)。作为示例而不是限制的方式，社交网络系统160可 对文本查询“在帕洛阿尔托的朋友(friends in palo alto)”进行解析，以识 别下列n元语法：朋友(friends)；在(in)；帕洛(palo)；阿尔托(alto)； 在…的朋友(friends in)；在帕洛(in palo)；帕洛阿尔托(palo alto)；在 帕洛的朋友(friend in palo)；也在帕洛(in palo also)；在帕洛阿尔托的朋 友(friends in palo alto)。在具体实施方式中，每种n元语法均可包括文本 查询中的n项的连续序列。尽管本公开内容描述了以具体方式对具体查询 进行解析，然而本公开内容考虑以任意合适方式对任意合适查询进行解 析。

在具体实施方式中，社交网络系统160可针对在文本查询中识别的每 种n元语法确定或者计算该n元语法对应于社交图谱元素的得分。例如， 该得分可以是置信得分、概率、质量、排列、另一合适类型的得分或者其 任意组合。作为示例而不是限制的方式，社交网络系统160可确定n元语 法对应于社交图谱元素(诸如社交图谱200中的用户节点202、概念节点 204或者矢线206)的概率得分(也被简称为“概率”)。概率得分可表示n 元语法与具体社交图谱元素之间的相似性或者关联性级别。存在计算概率 的多种不同方式。本公开内容考虑计算在搜索查询中识别的n元语法的概 率得分的任意合适方法。在具体实施方式中，社交网络系统160可以确定 概率，p，对应于具体社交图谱元素的n元语法。概率、p、可以计算作 为对应于具体社交图谱元素的概率，k，给出的具体搜索查询，X。换言 之，概率可以计算作为p＝(k|X)。作为示例而不是限制性方式，n元语法对 应于社交图谱元素的概率可以计算作为表示为p_i,j,k的概率得分。输入可以 是文本查询X＝(x₁,x₂,...,x_N)，和一组类别。对于各个(i:j)和类别k，社交网 络系统160可以计算p_i,j,k＝p(class(x_i:j)＝k|X)。作为示例而不是限制的方式， 可以针对下列社交图谱元素对n元语法“斯坦福(stanford)”进行打分如 下：学校“斯坦福大学(Stanford University)”＝0.7；位置“加利福尼亚州 斯坦福(Stanford，California)”＝0.2；用户“Allen Stanford”＝0.1。作为 另一实例而不是限制性方式，可以针对以下社交图谱元素对n元语法“朋 友”进行打分如下：用户“朋友”＝0.9；电视秀“朋友”＝0.1。在具体实 施方式中，社交网络系统160可使用向前向后算法确定具体n元语法对应 于具体社交图谱元素的概率。对于文本查询中给出的n元语法，社交网络 系统160可使用之前的n元语法和后续的n元语法来确定对应于给出n元 语法的具体社交图谱元素。在具体实施方式中，可以使用识别的社交图谱 元素生成通过搜索引擎可执行的的查询命令。查询命令可以是具有接受具 体的论点的定义的功能的结构化语义查询。作为示例而不是限制性方式， 可以对文本查询“朋友我马克”进行解析以形成查询命令：相交(朋友 (我)，朋友(马克))。换言之，查询寻找使查询用户(“我”)与用户“马 克”相交的社交图谱中的节点(即，通过朋友类型矢线206连接到查询用 户的用户节点202和通过朋友类型矢线206连接到用于用户“马克”的用 户节点202的这些用户节点202)。尽管本公开内容描述了以具体方式确定 对应于社交图谱元素的n元语法，然而本公开内容考虑以任意合适方式确 定对应于社交图谱元素的n元语法。而且，尽管本公开内容描述了使用具 体类型的得分确定对应于社交图谱元素的n元语法，然而本公开内容考虑 使用任意合适类型的得分确定对应于社交图谱元素的n元语法。

在具体实施方式中，社交网络系统160可识别具有比矢线阈值概率更 大的概率的一条或者多条矢线206。所识别的矢线206中的每条均可对应 于n元语法中的至少一种。作为示例而不是限制性方式，如果 p_i,j,k＞p_{edge-threshold}，那么n元语法可以仅被识别为对应于矢线，k。此外， 所识别的矢线206中的每条均可连接到所识别节点中的至少一个。换言之， 社交网络系统160仅可识别矢线206或者连接到用户节点202的矢线类型 或者之前被识别为对应于具体n元语法的概念节点204。未连接到任一之 前识别节点的矢线206或者矢线类型通常不可能对应于搜索查询中的具体 n元语法。通过过滤或者忽略这些矢线206和矢线类型，社交网络系统160 可更为有效地搜索社交图谱200以获得相关的社交图谱元素。作为示例而 不是限制性方式，参考图2，用于包含“就读于斯坦福”的文本查询，其 中，识别的概念节点204是学校“斯坦福”，社交网络系统160可以识别 对应于“在...工作”的矢线206和对应于“参加”的矢线206，两个矢线 206均连接到用于“斯坦福”的概念节点204。因此，n元语法“就读于” 可以被识别为对应于这些矢线206。然而，对于相同的文本查询，因为“斯 坦福(Stanford)”节点并不具有与其连接的任意这种矢线，所以社交网络 系统160可以不识别社交图谱200中对应于“喜欢”或者“迷恋”的矢线 206。尽管本公开内容描述了以具体方式识别对应于n元语法的矢线206， 然而本公开内容考虑以任意合适方式识别对应于n元语法的矢线206。

在具体实施方式中，社交网络系统160可识别具有比节点阈值概率更 大的概率的一个或者多个用户节点202或概念节点204。所识别节点中的 每个均可对应于n元语法中的至少一种。作为示例而不是限制性方式，如 果p_i,j,k＞p_{node-threshold}，那么n元语法可以仅被识别为对应于节点，k。而且， 所识别的用户节点202或者概念节点204中的每个均可连接到所识别的矢 线206中的至少一条。换言之，社交网络系统160仅可识别连接到之前被 识别为对应于具体n元语法的矢线206的识别节点或者节点类型。未连接 到任意之前识别矢线206的节点或者节点类型通常不可能对应于搜索查询 中的具体n元语法。通过过滤或者忽略这些节点和节点类型，社交网络系 统160可更为有效地搜索社交图谱200以获得相关社交图谱元素。作为示 例而不是限制的方式，对于包含“就职于苹果”的文本查询，其中，所识 别的矢线206是“就职于”，社交网络系统160可识别对应于苹果公司的 概念节点204，对应于苹果公司的概念节点204可具有与其连接的“就职 于”的多条矢线206。然而，对于相同的文本查询，社交网络系统160可 以不识别对应于水果类型“苹果”的概念节点204，对应于水果类型“苹 果”的概念节点204可具有与其连接的多条“喜欢”或者“迷恋”矢线， 但不具有“就职于”的矢线连接。在具体实施方式中，节点阈值概率对于 用户节点202和概念节点204可以不同，并且甚至在这些节点当中可以不 同(例如，一些概念节点204可以具有与其他概念节点204不同的节点阈 值概率)。作为示例而不是限制性方式，如果p_i,j,k＞p_{user-node-threshold}，那么n 元语法可以被识别为对应于用户节点302，k_user，然而如果 p_i,j,k＞p_{concept-node-threshold}，那么n元语法可以识别为对应于概念节点304，k_concept。 在具体实施方式中，社交网络系统160可仅识别位于对应于第一用户(即， 查询用户)的用户节点202的阈值间隔度内的节点。例如，该阈值间隔度 可以是一、二、三或者全部。尽管本公开内容描述了以具体方式识别对应 于n元语法的节点，然而本公开内容考虑以任意合适方式识别对应于n元 语法的节点。

在具体实施方式中，社交网络系统160可访问包括多种语法的与上下 文无关的语法模型。语法模型的每个语法可以包括一个或多个非终端令牌 (或者“非终端符号”)和一个或多个终端令牌(或者“终端符号”/“查 询令牌”)，其中，具体的非终端令牌可以由终端令牌替代。语法模型是用 于正式语言字串的一组信息规则。在具体实施方式中，多种语法可以被形 象化为组织为有序树的语法森林，具有对应于非终端令牌的内部节点和对 应于终端令牌的叶节点。各种语法可以表示为语法森林内的子树，其中语 法通过非终端令牌彼此邻接。因此，两种或更多语法可以是语法森林内的 子森林。尽管本公开内容描述了访问具体语法，然而本公开内容考虑任意 合适的语法。

在具体实施方式中，社交网络系统160可以使用一种或多种语法生成 一个或多个字串。为了生成语言形式的字串，以仅由单一起始符号构成的 字串开始。然后，按照任意顺序应用生成规则，直至不再生成既不包含起 始符号又不包含指定非终端符号的字串为止。在与上下文无关的语法中， 语法的各个非终端符号的生成与由语法的其他非终端符号生成的字串无 关。非终端符号可以被终端符号(即，终端令牌或者查询令牌)替换。如 上所述，查询令牌中的一些可对应于所识别节点或者所识别的矢线。通过 语法生成的字串则可被用作用于包含对所识别节点或者所识别的矢线的 引用的结构化查询的基础。通过语法生成的字串可以自然语言句法渲染， 使得基于字串的结构化查询也以自然语言渲染。与上下文无关的语法是其 中每种生成规则的左手侧仅由单个非终端符号构成的语法。概率性的与上 下文无关的语法是元组<Σ,N,S,P>，其中，分离集Σ和N分别利用为开始符 号的S∈N指定终端合非终端符号。P是产物集，其采用E→ξ(p)、与 E∈N,ξ∈(Σ∪N)⁺、及p＝Pr(E→ξ)的形式，E将扩展至字串ξ的概率。通过 给出的非终端E的所有的扩展的可能性的总和p必须是一。尽管本公开内 容描述了以具体方式生成字串，然而，本公开内容考虑以任意合适方式生 成字串。

在具体实施方式中，社交网络系统160可识别对应于之前所识别节点 和矢线的一种或多种查询令牌。换言之，如果识别的节点或者识别的矢线 可被用作具体语法中的查询令牌，则通过社交网络系统160可识别该查询 令牌。作为示例而不是限制的方式，示例性语法可以是：[用户][用户过滤 器][学校]。非终端符号[用户]、[用户过滤器]、和[学校]则可以基于所接收 的文本查询中的n元语法确定。例如，对于文本查询“朋友斯坦福”，可 以通过使用语法如“[朋友][谁就读于][斯坦福大学]”或者“[朋友][就职 于][斯坦福大学]”对该查询进行解析。作为另一实例而不是限制性方式， 示例性语法可以是[用户][用户过滤器][位置]。例如，对于文本查询“朋友 斯坦福”，可以通过使用语法如“[朋友][生活在][加利福尼亚州斯坦福]” 对该查询进行解析。在上述两种示例性情况下，如果接收文本查询中的n 元语法可被用作查询令牌，则通过社交网络系统160可识别这些查询令牌。 尽管本公开内容描述了以具体方式识别具体查询令牌，然而，本公开内容 考虑以任意合适方式识别任意合适的查询令牌。

在具体实施方式中，社交网络系统160可选择具有对应于之前所识别 节点和矢线的每个的至少一个查询令牌的一种或者多种语法。根据在文本 查询中识别的n元语法仅可以使用具体的语法。因此应该检查所有的可用 语法的终端令牌以找到与来自文本查询的识别的n元语法匹配的那些。换 言之，如果具体的语法可以使用所有识别的节点和矢线作为查询令牌，那 么可以通过社交网络系统160选择语法作为可能的语法用于生成结构化查 询。这是自底至上解析的有效类型。其中，使用可能的查询令牌确定适用 于该查询的可应用语法。作为示例而不是限制性方式，对于文本查询“朋 友斯坦福”，社交网络系统可以识别[朋友]和[斯坦福大学]的查询令牌。如 先前论述的，可以确定来自语法模型的语法的终端令牌。然后可以选择能 够使用[朋友]和[斯坦福大学]令牌的任意语法。例如，可以选择语法[用 户][用户过滤器][学校]，因为该语法可以使用[朋友]和[斯坦福大学]令牌作 为查询令牌，诸如通过形成字串“就读于斯坦福大学的朋友”或者“就职 于斯坦福大学的朋友”。因此，如果接收的文本查询中的n元语法可被用 作语法的查询令牌，则通过社交网络系统160可选择这些语法。类似地， 如果接收的文本查询包括不可以用作语法的查询令牌的n元语法，则可以 不选择该语法。尽管本公开内容描述了以具体方式选择具体语法，然而本 公开内容考虑以任意合适方式选择任意合适语法。

在具体实施方式中，社交网络系统160通过分析通过多个语法形成的 语法森林可以选择一种或多种语法。语法森林可以组织作为包括多个非终 端令牌和多个终端令牌的有序树。每个语法可以表示为语法森林内的子 树，并且每个子树可以经由一个或多个另外的非终端令牌与其他子树邻 接。作为示例而不是限制性方式，社交网络系统160可以通过识别语法森 林中对应于识别的节点的所有的终端令牌(即，查询令牌)和对应于文本 查询的部分的矢线开始。一旦语法森林中的这些查询令牌被识别，社交网 络系统160则可以从这些查询令牌的每个遍历语法森林向上以识别一个或 多个相交的非终端令牌。一旦非终端令牌被识别，其中来自所有的查询令 牌的路径相交，那么可以选择相交的非终端令牌，然后可以选择与语法森 林中的相交的非终端令牌邻接的一种或多种语法。尽管本公开内容描述了 以具体方式选择语法，然而本公开内容考虑以任意合适方式选择语法。

图5A示出示例性语义树。在具体实施方式中，社交网络系统160可 以对应于来自查询用户的文本查询生成语义树。语义树可包括对应于先前 识别的节点或者矢线的每个识别的查询令牌，并且还可以包括相交的令 牌。语义树还可以包括如适当连接查询令牌至相交令牌的非终端令牌。作 为示例而不是限制性方式，文本查询“朋友斯坦福”可以被解析为查询命 令：使(学校(斯坦福大学)，朋友(我))相交。换言之，查询寻找使查 询用户(“我”)的朋友(即，通过朋友类型矢线206连接到查询用户的用 户节点202的这些用户节点202)与用于斯坦福大学的概念节点204相交 的社交图谱中的节点。这可以表示为在图5A中示出的语义树，语义树包 括用于查询用户[我]、和学校[斯坦福]的终端令牌、用于[[用户]的朋友]的 非终端令牌、和相交令牌。在具体实施方式中，树中的每个令牌可按其被 处理的顺序标注。例如，在图5A中示出的语义树具有使用后缀表示法标 注的令牌，其中，用于[斯坦福]的令牌标注为(0，0)，用于[我]的令牌标 注为(1，1)，[[用户]的朋友]的令牌标注为(2)，和相交令牌标注为(3)。 尽管本公开内容描述了以具体方式生成具体语义树，然而本公开内容考虑 以任意合适方式生成任意合适语义树。

图5B示出示例性语法森林。在具体实施方式中，社交网络系统160 可以分析包括多个语法的语法森林以识别一组或多组非终端令牌和基本 上与对应于查询的语义树匹配的查询令牌，其中，每组具有对应于语义树 的相交令牌的非终端令牌。社交网络系统160然后可以选择语法森林中与 对应于相交令牌的非终端令牌邻接的一种或多种语法。从语法森林选择的 每个相交非终端令牌则可以被标注为语法的[开始]令牌。作为示例而不是 限制性方式，以下算法可以用于遍历语法森林以识别相交令牌：

对于语义树中的每个终端令牌(i，i)，标注语法森林中的每个匹配的 终端令牌(i，i)。

对于i＝0至大小(语义树-1):

对于j＝i至0:

扩展所有标注(i，j)的令牌。

扩展(i，j)：

对于语法森林中的所有令牌：

如果令牌具有规则，该规则具有使子树增长至(i’，j’)的1自变数， 则将令牌标注为(i’，j’)；

如果令牌具有规则，规则具有可使子树增长的多于1自变数，将令牌 标注为“等待”；

如果令牌被标注为“等待”，那么现在可以使子树增长至(i’，j’)， 然后将令牌标注为(i’，j’)。

因此，例如，在图5B中示出的示例中，与来自在图5A中示出的语 义树的终端令牌(0，0)和(1，1)匹配的所有的终端令牌可以分别标注 为(0，0)和(1，1)。然后，从语法森林中的每个有效的令牌，社交网 络系统160可以遍历源(parent)令牌以查看是否可以形成与语义树匹配 的子树。如果源非终端令牌具有匹配的语义，那么可以使用与来自语义树 的对应的令牌相同的标注来标注非终端令牌。在图5B中示出的示例中， 因为语法森林从标注(1，1)的令牌之一遍历，一旦发现与语义[[用户] 的朋友]匹配的非结符令牌，那么令牌可以标注为(2)，因此其与语义树 匹配。该令牌的源然后可以标注为“等待”，因为其为潜在的相交令牌。 然而，如果遍历未能发现与语义树的语义匹配的任意源令牌，那么可以终 止具体遍历。一旦遍历的一个分支达到潜在的相交令牌，那么该令牌可以 被标注为“等待”，同时算法利用来自其他有效的终端令牌的遍历(例如， 来自标注为(0，0)的终端令牌的遍历)进行。替代地，如果遍历找到已 被标注为“等待”的令牌，那么该令牌可以被识别为相交令牌并且标注为 (3)。标注为(3)的每个令牌然后可以被选为语法，语法可以用于生成 自然语言字串用于结构化查询。算法将试图找到语法森林中引导至相交令 牌的的最低成本的多路径，并且可以通过其他相交令牌(如果有的话)优 先选择对应于该最低成本多路径的相交令牌。尽管本公开内容描述了以具 体方式分析具体语法森林，然而本公开内容考虑以任意合适方式分析任意 合适语法森林。

在具体实施方式中，社交网络系统160可确定每种选择的语法的得分。 例如，该得分可以是置信得分、概率、质量、排列、另一合适类型的得分 或者其任意组合。得分可以基于与所选择的语法中使用的查询令牌相关联 的个体得分或者概率。如果使用具有相对较高个体得分的查询令牌，则语 法可具有相对较高的得分。作为示例而不是限制的方式，继续之前示例， 可以针对下列社交图谱元素对n元语法“斯坦福”进行打分如下：学校“斯 坦福大学”＝0.7；位置“加利福尼亚州斯坦福”＝0.2；用户“Allen Stanford” ＝0.1。可以针对以下社交图谱元素对n元语法“朋友”进行打分如下：用 户“朋友”＝0.9；电视秀“朋友”＝0.1。因此，如果使用用于用户“朋友” 和学校“斯坦福大学”的查询令牌(例如，生成字串“就读于斯坦福大学 的朋友”)(两者皆具有相对较高的个体得分)，则语法[用户][用户过滤 器][学校]可具有相对较高的得分。与此相反，如果使用用于用户“朋友” 和用户“Allen Stanford”的查询令牌(例如，生成字串“Allen斯坦福的 朋友”)，则因为后者查询令牌具有相对较低的个体得分，所以语法[用 户][用户过滤器][用户]可能具有相对较低的得分。在具体实施方式中，社 交网络系统160可以基于遍历的路径的长度确定选择的语法的得分以识别 对应于所选择的语法的相交令牌。利用最低成本多路径(即，较短路径) 的语法可以比利用高成本多路径(即，较长路径)得分更高。在具体实施 方式中，社交网络系统160可基于广告赞助确定所选择的语法的得分。广 告商(诸如，对应于具体节点的具体资料页面的用户或者管理人员)可以 赞助具体节点使得包括引用赞助的节点的查询令牌的语法可以具有更高 的得分。尽管本公开内容描述了以具体方式确定具体语法的具体得分，然 而本公开内容考虑以任意合适方式确定任意合适语法的任意合适得分。

在具体实施方式中，社交网络系统160可基于对应于语法的查询令牌 的社交图谱元素与查询用户(即，第一用户，对应于第一用户节点202) 的关联性确定选择的语法的得分。用户节点202和通过矢线206直接连接 到第一用户节点202的概念节点204可被视为与第一用户相关。因此，包 括对应于这些相关节点和矢线的查询令牌的语法可被视为更与查询用户 相关。作为示例而不是限制的方式，通过矢线206连接到第一用户节点202 的概念节点204可被视为与第一用户节点202相关。如此处使用的，当参 考社交图谱200时，术语“连接”指社交图谱200中的两个节点之间存在 路径，其中，该路径可包括一条或者多条矢线206和零个或者多个中间节 点。在具体实施方式中，经由一个或者多个中间节点(并且由此两条或者 多条矢线206)连接到第一用户节点202的节点也可被视为与第一用户相 关。而且，在具体实施方式中，第二节点越接近于第一用户节点，第二节 点越被视为与第一用户节点相关。即，使第一用户节点202与具体用户节 点202或者概念节点204隔离的矢线206越少(即，间隔度越少)，则用 户节点202或者概念节点204越被视为与第一用户相关。作为示例而不是 限制性方式，如在图2中示出的，对应于学校“斯坦福”的概念节点204 连接到对应于用户“C”的用户节点202，因此，概念“斯坦福”可以被 认为与用户“C”相关。作为另一示例而不是限制性方式，对应于用户“A” 的用户节点202经由一个中间节点和两条矢线206连接到对应于用户“C” 的用户节点202(即，对应于用户“B”的中间用户节点202)，因此，用 户“A”可以被认为与用户“C”相关，但是因为用于用户“A”的用户节 点202针对用户“C”是二级链接，所以该具体概念节点204可以被认为 比通过单个矢线206连接到用于用户“C”的用户节点的用户节点202(诸 如，对应于用户“B”的用户节点202)较少相关。还作为另一示例而不 是限制性方式，用于“在线Poker”的概念节点(其可以对应于在线多人 游戏)未通过社交图谱200中的任意路径连接到用于用户“C”的用户节 点，因此，概念“在线Poker”可能不被认为与用户“C”相关。在具体实 施方式中，如果第二节点在第一用户节点202的阈值间隔度内，第二节点 可以仅被认为与第一用户相关。作为示例而不是限制性方式，如果阈值间 隔度是三，那么对应于用户“D”的用户节点202可以被认为与对应于食 谱“巴马芝士吉列鸡扒(chicken parmesan)”的概念节点204相关，这两 个节点在图2中示出的社交图谱200上在彼此的三级内。然而，继续该示 例，对应于应用“全部关于食谱”的概念节点204不被认为与对应于用户 “D”的用户节点202相关，因为这些节点是社交图谱200中的四级隔离。 尽管本公开内容描述了以具体方式确定具体社交图谱元素(并且由此的其 对应的查询令牌)是否彼此相关，然而，本公开内容考虑以任意合适方式 确定任意合适的社交图谱元素是否彼此相关。而且，尽管本公开内容描述 了确定对应于用户节点202和概念节点204的具体查询令牌是否与查询用 户相关，然而本公开内容同样考虑确定任意合适的查询令牌(并且由此任 意合适的节点)是否与任意其他合适的用户相关。

在具体实施方式中，社交网络系统160可基于对应于语法的查询令牌 的社交图谱信息确定选择的语法的得分。作为示例而不是限制性方式，当 确定概率，p，时，那么对应于具体社交图谱元素的n元语法，概率的计 算也可以作为社交图谱信息中的因素。因此，对应于具体社交图谱元素的 概率，k，给出的具体搜索查询，X，和社交图谱信息，G可以计算为 p＝(k|X,G)。然后，使用识别的节点和矢线的个体概率可确定将这些社交 图谱元素作为查询令牌的语法的得分。在具体实施方式中，选择的语法的 得分可基于第一用户节点202与作为语法查询令牌而使用的具体社交图谱 元素之间的间隔度。具有对应于在社交图谱200中与查询用户(即，该元 素与第一用户节点202之间的间隔度更小)较近的社交图谱元素的查询令 牌的语法比使用对应于与用户更远的(即，更大间隔度)社交图谱元素的 查询令牌的语法得分更高。作为示例而不是限制性方式，参考图2，如果 用户“B”输入文本查询“小鸡(chicken)”，具有对应于用于通过矢线206 连接到用户“B”的食谱“巴马芝士吉列鸡扒”的概念节点204的查询令 牌的语法可以具有比具有对应于与在社交图谱200中未连接到用户“B” 的n元语法鸡肉(例如，对应于“鸡块(chicken nugget)”或者“古怪的 小鸡舞(funky chicken dance)”的概念节点204)相关联的其他节点的查 询令牌的语法相对较高的得分。在具体实施方式中，选择的语法的得分可 基于对应于语法的查询令牌的识别矢线206。如果社交网络系统160已经 识别对应于接收文本查询中的n元语法的一条或者多条矢线，则当通过语 法确定文本查询的具体解析得分时，可考虑这些识别的矢线。如果具体语 法包括对应识别的节点和识别的矢线的查询令牌，如果识别的节点实际上 不连接到识别的矢线中的任一条，则该具体语法可被分配零分或者空白 分。在具体实施方式中，选择的语法的得分可以基于连接到对应于语法的 查询令牌的节点的矢线206的条数。包括对应于具有更多连接矢线206的 节点的查询令牌的语法可能更受欢迎并且更可能成为搜索查询的目标。作 为示例而不是限制性方式，如果用于“斯坦福，加利福尼亚”的概念节点 204仅通过五条矢线连接，而用于“斯坦福大学(stanford university)”的 概念节点204通过五千条矢线连接，当确定包含对应于这些节点的任一个 的查询令牌的语法的得分时，社交网络系统160可以确定具有对应于用于 “斯坦福大学”的概念节点204的查询令牌的语法具有比引用用于“斯坦 福，加利福尼亚”的概念节点204的语法相对高的得分，因为更多的矢线 数量连接到前概念节点204。在具体实施方式中，所选择的语法的得分可 以基于与第一用户(即，查询用户)相关联的搜索历史。具有对应于第一 用户之前已经访问或者与第一用户之前已经访问的节点相关的节点的查 询令牌的语法更为可能成为第一用户搜索查询的目标。因此，这些语法可 被给定更高的得分。作为示例而不是限制性方式，如果第一用户之前访问 “斯坦福大学”资料页面，但是从未访问“斯坦福，加利福尼亚”资料页 面，当确定具有对应于这些概念的查询令牌的语法的得分时，社交网络系 统160可以确定用于“斯坦福大学”的概念节点204具有相对高的得分， 并且因此使用对应的查询令牌的语法，因为查询用户之前访问用于学校的 概念节点204。作为另一示例而不是限制性方式，如果第一用户之前访问 用于电视秀“朋友”的概念资料页面，当确定具有对应于该概念的查询令 牌的语法的得分时，社交网络系统160可以确定对应于电视秀“朋友”的 概念节点204具有相对高的得分，并且因此使用对应的查询令牌的语法， 因为查询用户之前访问用于该电视秀的概念节点204。尽管本公开内容描 述了以具体方式基于具体社交图谱信息确定具体语法的得分，然而本公开 内容考虑以任意合适方式基于任意合适的社交图谱信息确定任意合适语 法的得分。

在具体实施方式中，社交网络系统160可选择具有比语法阈值得分更 高的得分的一种或者多种语法。所选择语法中的每种均可包含对应于识别 的节点或者识别的矢线中的每个的查询令牌(对应于接收文本查询的n元 语法)。在具体实施方式中，可基于其确定得分排列语法，并且仅可选择 位于阈值排序内的语法(例如，前七个)。尽管本公开内容描述了以具体 方式选择语法，然而本公开内容考虑以任意合适方式选择语法。

在具体实施方式中，社交网络系统160可生成对应于所选择的语法(例 如，具有比语法阈值得分更高的得分的这些语法)的一项或多项结构化查 询。每个结构化查询均可基于通过对应选择语法生成的字串。作为示例而 不是限制的方式，语法[用户][用户过滤器][学校]可响应文本查询“朋友斯 坦福”生成“就读于斯坦福大学的朋友“的字串，其中，语法中的非终端 令牌[用户]、[用户过滤器]、[学校]被终端令牌[朋友]、[谁就读于]以及[斯 坦福大学]替换，以生成字串。在具体实施方式中，通过使用自然语言句 法的语法生成的字串可以渲染为以自然语言形式的结构化查询。作为示例 而不是限制性方式，来自之前示例的结构化查询使用终端令牌[谁就读于]， 该终端令牌使用自然语言句法使得通过语法渲染的字串为自然语言。通过 语法生成的自然语言字串然后可以通过修改对应于社交图谱元素的查询 令牌被渲染以形成结构化查询以包括对这些社交图谱元素的引用。作为示 例而不是限制性方式，字串“就读于斯坦福大学的朋友”可以被渲染使得 用于“斯坦福大学”的查询令牌出现在结构化查询中作为对对应于学校“斯 坦福大学”的概念节点204的引用，其中，引用可以包括高亮、内联链接、 片断、另一合适的引用、或者其任意组合。每个结构化查询均可包括对应 于相应选择语法的查询令牌，其中，这些查询令牌对应于识别的矢线206 中的一条或者多条和识别的节点中的一个或者多个。下面更多地描述了生 成结构化查询。

在具体实施方式中，社交网络系统160可以生成一个或多个查询修改 用于使用与上下文无关的语法模型的结构化查询。以下更多地论述查询修 改。查询修改可以引用一个或多个额外的节点或者一个或多个额外的矢 线。这种类型的查询修改可以用于细化结构化查询或者使结构化查询变狭 窄。替代地，查询修改可以引用一个或多个替代的节点或者一个或多个替 代的矢线。这种类型的查询修改可以用于以结构化查询为中心或者使结构 化查询变宽。总体来说，这些可以称为修改节点和修改矢线，其中，修改 是对对应于社交图谱元素的具体查询令牌的添加或替换。查询修改中对另 外的或者替代的节点和矢线的引用可以分别用于添加或替换结构化查询 中的查询令牌。为了识别用于结构化查询的可能的查询修改，社交网络系 统160可以从最初的结构化查询中识别具有对应于所述选择的节点和所述 选择的矢线的查询令牌的一个或多个语法。换言之，社交网络系统160可 以识别实际用于生成具体的结构化查询的语法，可以生产该结构化查询的 其他语法，和可以使结构化查询作为另一结构化查询的部分的语法。社交 网络系统160然后可以识别在结构化查询中可以添加或者替代的这些语法 中的查询令牌。这些另外的或者替代的查询令牌然后可以用来生成建议的 查询修改，生成的建议的查询修改可以被传输到查询用户作为搜索结果页 面的部分。查询用户然后可以选择这些查询修改的一种或多种，并且作为 响应，社交网络系统160可以生成新的结构化查询(和对应的搜索结果)。 在适当的情况下，该新的结构化查询可包括修改查询令牌(即，另外的或 者替代的查询令牌)。尽管本公开内容描述了以具体方式生成查询修改， 然而，本公开内容考虑以任意合适方式生成查询修改。

图6示出了用于使用与上下文无关的语法模型来生成自然语言结构化 搜索查询的示例性方法600。该方法可从步骤610开始，即，社交网络系 统160可访问包括多个节点和连接节点的多条矢线206的社交图谱200。 节点可包括第一用户节点202和多个第二节点(一个或者多个用户节点 202、概念节点204、或者其任意组合)。在步骤620，社交网络系统160 可从第一用户接收非结构化文本查询。文本查询可包括一种或者多种n元 语法。在步骤630，社交网络系统160可以识别对应于非结构化文本查询 的至少一部分的矢线和第二节点。例如，社交网络系统160可以识别对应 于来自查询的具体n元语法的矢线和节点。在步骤640，社交网络系统160 可访问包括多种语法的与上下文无关的语法模型。每种语法可以包括一个 或多个非终端令牌和一个或多个查询令牌(即，终端令牌)。在步骤650， 社交网络系统160可以识别多种语法中的一个或多个查询令牌，其中，每 个识别的查询令牌对应于识别的节点或者识别的矢线之一。在步骤660， 社交网络系统160可以选择一种或多种语法，其中，每种选择的语法包括 对应于识别的矢线和识别的第二节点的每个的至少一个查询令牌。在步骤 670，社交网络系统可基于所选择的语法生成一项或者多项结构化查询。 每项结构化查询可以对应于通过所选择的语法生成的字串，字串可以使用 自然语言句法。每项结构化查询可包括对识别的矢线和识别的第二节点的 每个的引用。在适当的情况下，具体实施方式可重复图6中的方法的一个 或者多个步骤。尽管本公开内容描述并且示出了图6中以具体顺序发生的 方法的具体步骤，然而本公开内容考虑图6中以任意合适顺序发生的方法 的任意合适步骤。而且，尽管本公开内容描述并且示出了执行图6中的方 法的具体步骤的具体组件、设备、或者系统，然而本公开内容考虑执行图 6中的方法的任意合适步骤的任意合适组件、设备、或者系统的任意合适 组合。

从于2012年11月12日提交的美国专利申请第13/674695号中可以获 得关于使用具有搜索查询的语法模型的更多信息，将其通过引用结合在 此。

生成结构化搜索查询

在具体实施方式中，社交网络系统160可生成一项或者多项结构化查 询，其中每项均可包括对应语法的查询令牌，其中，查询令牌可对应于识 别的用户节点202中的一个或者多个或者识别的矢线206中的一条或者多 条。如之前描述的，生成的结构化查询可基于通过一项或多项与上下文无 关的语法生成的自然语言字串。这种类型的结构化搜索查询可允许社交网 络系统160通过搜索连接到识别的用户节点202和识别的矢线206或者以 其他方式与识别的用户节点202和识别的矢线206有关的内容而更为有效 地搜索与在线社交网络有关的资源和内容(诸如，资料页面等)。作为示 例而不是限制的方式，社交网络系统160可响应文本查询“给我介绍我女 朋友的朋友”生成结构化查询“Stephanie的朋友”，其中，结构化查询中 的“朋友”和“Stephanie”是对应于具体社交图谱元素的引用。对“Stephanie” 的引用对应于具体用户节点202，而对“朋友”的引用对应于将用户节点 202连接到其他用户节点202的“朋友”矢线206(即，连接到“Stephanie 的”第一重要程度朋友的矢线206)。当执行该结构化查询时，社交网络系 统160可以识别通过“朋友”矢线206连接到对应于“Stephanie”的用户 节点202的一个或多个用户节点202。在具体实施方式中，社交网络系统 160可生成多项结构化查询，其中，结构化查询可包括对不同识别用户节 点202或者不同识别矢线206的引用。作为示例而不是限制的方式，社交 网络系统160可响应文本查询“猫的照片”生成第一结构化查询“Catey 的照片”和第二结构化查询“Catherine的照片”，其中，结构化查询中的 “照片”是对应于具体社交图谱元素的引用，并且其中，“Catey”和 “Catherine”是两个不同用户节点202的引用。尽管本公开内容描述了以 具体方式生成具体结构化查询，然而本公开内容考虑以任意合适方式生成 任意合适结构化查询。

在具体实施方式中，社交网络系统160可生成一项或者多项结构化查 询，其中每项均包括对应于识别的概念节点204和识别的矢线206中的一 条或者多条的查询令牌。这种类型的结构化搜索查询可允许社交网络系统 160通过搜索连接到识别的概念节点204和识别的矢线206或者以其他方 式与识别的概念节点204和识别的矢线206有关的内容而更为有效地搜索 与在线社交网络有关的资源和内容(诸如，资料页面等)。作为示例而不 是限制的方式，社交网络系统160可响应文本查询“喜欢facebook的朋友” 生成结构化查询“喜欢facebook的我的朋友”，其中，结构化查询中的“朋 友”、“喜欢”以及“facebook”是对应于如之前描述的具体社交图谱元素 (即，“朋友”矢线206、“喜欢”矢线206以及“Facebook”概念节点204) 的查询令牌。在具体实施方式中，社交网络系统160可生成多项结构化查 询，其中，结构化查询可包括对不同识别的概念节点204或者不同识别的 矢线206的引用。作为示例而不是限制的方式，继续之前示例，除结构化 查询“喜欢Facebook的我的朋友”之外，社交网络系统160还可生成结 构化查询“喜欢Facebook烹饪团队(CulinaryTeam)的我的朋友”，其中， 结构化查询中的“Facebook烹饪团队(CulinaryTeam)”是对应于又一社 交图谱元素的查询令牌。在具体实施方式中，社交网络系统160可对生成 的结构化查询进行排列。可基于各种因素对结构化查询进行排列。在具体 实施方式中，社交网络系统160可以基于广告赞助者排列结构化查询。广 告商(诸如，对应于具体节点的具体资料页面的用户或者管理人员)可以 赞助具体节点使得引用节点的结构化查询可以具有排列的更靠前。尽管本 公开内容描述了以具体方式生成具体结构化查询，然而本公开内容考虑以 任意合适方式生成任意合适结构化查询。

在具体实施方式中，社交网络系统160可将结构化查询中的一项或者 多项传输给第一用户(即，查询用户)。作为示例而不是限制性方式，在 产生结构化查询之后，社交网络系统160可以将一项或多项结构化查询作 为响应传输(可以利用AJAX或者其他适用技术)至用户的客户端系统 130，结构化查询可包括例如，引用的社交图谱元素的名称(名称字串)， 其他查询限制(例如，布尔运算符等)，以及，潜在地，与引用的社交图 谱元素相关联的其他元数据。如图4A和图4B所示，查询用户的客户端 系统130上的网络浏览器132可在下拉菜单300中显示传输的结构化查询。 如上所述，在具体实施方式中，可按照排列顺序(例如，基于之前确定的 排序)将传输的查询呈现给查询用户。具有更佳排序的结构化查询可显示 在更为显著的位置。而且，在具体实施方式中，仅可将阈值排序以上的结 构化查询传输或者显示给查询用户。作为示例而不是限制的方式，如图4A 和图4B所示，可在下拉菜单300中将结构化查询呈现给查询用户，其中， 排序靠前的结构化查询可显示在菜单顶部，而排序靠后的结构化查询以降 序顺序显示在菜单中。在图4A和图4B所示的示例中，仅将排列在前七 项的查询传输并显示给用户。在具体实施方式中，结构化查询中的一个或 多个引用可以被高亮(例如，列出、加下划线、划圆圈、变粗体、变斜体、 加颜色、加亮度、平移、大写)以表示其与具体社交图谱元素的对应。作 为示例而不是限制的方式，如图4A和图4B所示，可以高亮(列出)结 构化查询中对“斯坦福大学”和“加利福尼亚州斯坦福”的引用，以表示 其对应于具体概念节点204。同样，还可高亮在下拉菜单300中显示的结 构化查询中的“朋友(Friends)”、“喜欢(like)”、“就职于(work at)”以 及“去(go to)”的引用，以指示其对应于具体矢线206。尽管本公开内容 描述了以具体方式传输具体结构化查询，然而本公开内容考虑以任意合适 方式传输任意合适结构化查询。

在具体实施方式中，社交网络系统160可从第一用户(即查询用户) 接收对结构化查询中的一项的选择。替代地，社交网络系统160可以接收 结构化查询作为在某一上下文中通过系统自动选择的查询(例如，默认选 择)。在接收的结构化查询中引用的节点和矢线可以分别称为选择的节点 和选择的矢线。作为示例而不是限制的方式，查询用户的客户端系统130 上的网络浏览器132可在下拉菜单300中显示传输的结构化查询，如图4A 和图4B所示，用户则可单击或者以其他方式选择(例如，通过其键盘上 的简单按键“回车”)，以表示用户希望社交网络系统160执行的具体结构 化查询。一旦选择具体结构化查询，用户的客户端系统130则可呼叫或者 以其他方式命令社交网络系统160执行选择的结构化查询。尽管本公开内 容描了以具体方式接收对具体结构化查询的选择，然而本公开内容考虑以 任意合适方式接收对任意合适结构化查询的选择。

从于2012年7月23日提交的美国专利申请第13/556072号中可以获 得关于结构化搜索查询的更多信息，将其通过引用结合在此。

生成搜索结果和片断(snippet)

图7A至图7G示出示例性搜索结果页面。响应于从查询用户(还称 为“第一用户”)接收的结构化查询，社交网络系统160可以生成一个或 多个搜索结果，其中，每个搜索结果与结构化查询的术语匹配(或者基本 上匹配)。在具体实施方式中，社交网络系统160可从查询用户(还称为 “第一用户”，对应于第一用户节点202)接收结构化查询。响应于结构化 查询，社交网络系统160可以生成对应于结构化查询的一个或多个搜索结 果。每个搜索结果可包括至资料页面的链接和资料页面的描述或概要(或 者对应于该页面的节点)。搜索结果可以作为搜索结果页面呈现并且传输 至查询用户。图7A至图7G示出响应于各种结构化查询生成的各种示例 性搜索结果页面。用于生成具体搜索结果页面的结构化查询在查询字段 350中示出，并且响应于结构化查询生成的各种搜索结果在结果字段710 中示出。在具体实施方式中，查询字段350还可以用作页面的标题栏。换 言之，标题栏和查询字段350可以有效的为搜索结果页面上的统一字段。 作为示例，图7G示出具有在查询字段350中的结构化查询“我的来自田 纳西州的朋友的照片”的搜索结果页面。该结构化查询还有效地用作用于 生成的页面的标题，其中，页面显示查询用户的来自田纳西州的朋友的多 张照片。搜索结果页面还可以包括修改字段720、建议搜索字段730、扩 展搜索字段740、或者消歧字段750。以下更多地论述这些另外的字段。 当生成搜索结果时，社交网络系统160可以生成用于每个搜索结果的一个 或多个片断，其中，片断是关于搜索结果的目标的上下文信息(即，关于 社交图谱实体、资料页面、或者对应于具体搜索结果的其他内容的上下文 信息)。在具体实施方式中，用于每个搜索结果的至少一个片断可以是世 系片断，其描述搜索结果如何与来自用于生成搜索结果的结构化查询的选 择的节点和选择的矢线匹配。这些世系片断提供关于具体搜索结果如何满 足针对社交图谱元素的结构化查询的术语的上下文。尽管本公开内容描述 和示出了具体搜索结果页面，然而本公开内容考虑任意合适的搜索结果页 面。而且，尽管本公开内容描述并示出以具体方式生成具体片断，然而本 公开内容考虑以任意合适方式生成任意合适片断。

在具体实施方式中，社交网络系统160可以生成对应于结构化查询的 一个或多个搜索结果。搜索结果可以识别匹配搜索查询或者可能与搜索查 询有关的资源或者内容(例如，用户资料页面、内容资料页面、或者外来 资源)。在具体实施方式中，每个搜索结果可以与社交图谱200的具体用 户节点202或者概念节点204对应。搜索结果可包括与节点相关联的资料 页面的链接，以及关于节点的上下文信息(即，关于对应于该节点的用户 或者概念的上下文信息)。作为示例而不是限制性方式，参考图7B，在查 询字段350中的结构化查询“我的就职于Facebook的朋友”生成在结果 字段710中示出的各种搜索结果。结果字段710中的每个搜索结果显示用 户的资料页面的链接(示出为用户的姓名，包含资料页面的内联链接)和 关于对应于社交图谱200的用户节点202的用户的上下文信息。作为示例 而不是限制性方式，参考图7G，在查询字段350中的结构化查询“我的 来自田纳西州的朋友的照片”生成在结果字段710中示出的各种搜索结果。 在图7G中示出的每个搜索结果显示对应于社交图谱的概念节点204的相 片的略图。在具体实施方式中，每个搜索结果可以与通过结构化查询的一 条或多条选择的矢线连接到一个或多个选择的节点的节点对应。作为示例 而不是限制性方式，参考图2，如果用户“C”提交结构化查询“喜欢Old  Pro的朋友”，该结构化查询引用位置“Old Pro”的朋友类型矢线206和概 念节点204，社交网络系统160可以返回对应于用户“B”的搜索结果， 因为用户“B”的用户节点202通过朋友类型矢线206连接到用户“C” 的用户节点202并通过喜欢类型矢线206连接到位置“Old Pro”的概念节 点204。在具体实施方式中，社交网络系统160还可以响应于结构化查询 传输广告或者其他推广内容至客户端系统130。广告可以作为搜索结果的 部分包括在搜索结果中，或者单独地包括在搜索结果中。广告可以对应于 搜索结果中引用的一个或多个对象。在具体实施方式中，社交网络系统160 可以基于与这些资源或者内容相关联的用户相关联的隐私设置过滤出识 别具体资源或者内容的一个或多个搜索结果。尽管本公开内容描述了以具 体方式生成搜索结果，然而，本公开内容考虑了以任意合适方式生成任意 合适的搜索结果。

在具体实施方式中，搜索结果可包括一个或多个片断。片断是关于搜 索结果的目标的上下文信息。换言之，片断提供关于对应于搜索结果的该 页面或者内容的信息。作为示例而不是限制性方式，片断可以是来自对应 于搜索结果的资料页面(或节点)的内容的样本。可以包括片断以及对于 任意合适类型的内容的搜索结果。在具体实施方式中，显示具有搜索结果 的片断可基于对应于搜索结果的内容的类型。作为示例而不是限制性方 式，如果查询用户搜索用户，那么包括搜索结果的片断可以是关于在搜索 结果中显示的用户的上下文信息，像用户的年龄、位置、教育、或者工作 单位。作为另一示例而不是限制性方式，如果查询用户搜索照片，那么包 括搜索结果的片断可以是关于在搜索结果中显示的照片的上下文信息，像 照片中的人或者对象的名称，照片的赞/访问的数目，或者拍摄照片的位置。 作为另一示例而不是限制性方式，如果查询用户搜索位置，那么包括搜索 结果的片断可以是关于在搜索结果中显示的位置的上下文信息，像位置的 地址，位置的操作时间，或者位置的赞/签到数目。片断中提供的信息可以 由目标页面的拥有者/管理人员选择，或者可以由社交网络系统160自动地 选择。片断可以用于显示关于搜索结果的关键信息，诸如图像略图、概要、 文献类型、访问量、评论、日期、发起人、等级级别、价格、或者其他相 关信息。在具体实施方式中，用于对应于在线社交网络中的用户/概念的搜 索结果的片断可包括由在线社交网络的用户提供的或在在线社交网络上 可用的上下文信息。作为示例而不是限制性方式，片断可包括以下类型的 信息的一种或多种：群组的隐私设置；群组中的成员的数目；推广消息(例 如，渲染为片断的内联广告单元)；页面种类；实际地址；履历详情；兴 趣；婚姻状况；性取向/偏好；性别/性别；年龄；生日；目前所在城市； 教育背景；政治面貌；宗教信仰；工作经历；使用过的应用程序；评论； 标签；其他合适的上下文信息；或者它们的任意组合。在具体实施方式中， 片断可包括对来自社交图谱200的节点或者矢线的引用。这些片断可以被 高亮以表示对应于社交图谱元素的引用。作为示例而不是限制性方式，图 7F示出用户“Sol”的搜索结果，其中，该搜索结果的片断之一是“例如 Reposado，The Slanted Door，及12个其它的”。在该示例中，术语“Reposado” 和“The Slanted Door”被高亮(加下划线)以表示它们是对对应于概念 “Reposado”和“The Slanted Door”的概念节点204的引用，它们是用户 “Sol”喜欢的餐馆(即，用于“Sol”的用户节点202通过喜欢类型矢线 206连接到用于“Reposado”和“The Slanted Door”的概念节点204)。在 该示例中高亮的引用还包含对应于“Reposado”和“The Slanted Door”的 概念资料页面的内联链接。在具体实施方式中，社交网络系统160可以基 于与通过搜索结果识别的用户相关联的隐私设置过滤出用于搜索结果的 一个或多个片断。尽管本公开内容描述或者示出了片断的具体类型，但是 本公开内容考虑了任意合适的片断类型。

在具体实施方式中，搜索结果可包括至少一个片断，该至少一个片断 包括对结构化搜索查询的选择的节点和选择的矢线的一个或多个引用。换 言之，响应于结构化搜索查询，社交网络系统160可以生成具有提供与搜 索结果如何与搜索查询匹配相关的上下文信息的片断的搜索结果。这些可 以称为世系片断，因为它们提供使具体搜索结果如何与结构化查询的社交 图谱元素相关上下文化的社交图谱信息(节点/矢线关系信息)。换言之， 世系片断是向查询用户提供具体搜索结果满足结构化查询的证据的方式。 作为示例而不是限制性方式，图7D示出用于结构化查询“我的就职于 Facebook和就职于Acme作为软件工程师的朋友”的搜索结果页面。在结 构化查询中引用的社交图谱元素包括“我的朋友”(即，用户节点202通 过朋友类型矢线206连接到查询用户的节点)，“就职于Facebook(即，用 户节点202通过就职于类型矢线206连接到用于“Facebook”的概念节点 204)，和“就职于Acme”(即，用户节点202通过就职于类型矢线206连 接到用于“Acme”的概念节点204)。在图7D中示出的用于“Luke”的 第一搜索结果包括陈述“Facebook的工程总监”的片断，对应于来自结构 化查询的“就职于Facebook”令牌。因此，该片断显示用于“Luke”的搜 索结果满足结构化查询的“就职于Facebook”要求，因为“Luke”是 “Facebook的工程总监”。“Luke”搜索结果中的其他片断提供示出搜索结 果如何满足结构化查询的其他标准的进一步上下文。换言之，用于“Luke” 的用户节点202通过就职于类型矢线206连接到用于“Facebook”的概念 节点204。在具体实施方式中，世系片断可包括以下类型的社交图谱信息 的一种或多种：参加的学校；就职于/就职在；喜欢的页面；使用过的应用 软件；订阅；被订阅；家庭关系；关系连接(与...结婚；日期；等)；住在 /住在...附近；签到的地点；参观过的地点；住在位置处的朋友的数目；在 位置处学习的朋友的数目；是群组的成员的朋友；赞的数目；谈论到页面 的人的数目；订阅者的数目；使用应用程序的朋友；应用程序的用户的数 目；在媒体中加标签的人；评论媒体/在媒体中评论的人；创建媒体的人； 其他合适的社交图谱信息；或者它们的任意组合。在具体实施方式中，可 以高亮对世系片断中的选择的节点或者选择的矢线的一个或多个引用以 表示对应于选择的节点或者选择的矢线的引用。尽管本公开内容描述了世 系片断的具体类型，但是本公开内容考虑了任意合适的世系片断类型。

在具体实施方式中，搜索结果可包括片断，该片断包括对通过一条或 多条矢线206连接到查询用户的用户节点202的一个或多个节点的引用。 换言之，搜索结果可包括具有关于搜索结果如何与查询用户的朋友相关或 者与连接到用户的概念节点204相关的上下文信息的片断。这些可以称为 社交片断，因为它们提供使具体搜索结果如何连接到查询用户和/或用户的 朋友/兴趣上下文化的社交图谱信息(节点/矢线关系信息)。作为示例而不 是限制性方式，图7D示出用于结构化查询“我的就职于Facebook和就职 于Acme作为软件工程师的朋友”的搜索结果页面。在图7D中示出的用 于“Luke”的第一搜索结果包括陈述“你的自2009年4月以来的朋友” 的片断。该片断提供关于“Luke”搜索结果如何与查询用户相关的上下文 信息。换言之，用于“Luke”的用户节点202通过朋友类型矢线206连接 到查询用户的节点。“Luke”搜索结果还包括陈述“包括Sol和Steven的 197个相互的朋友”的片断。该片断提供关于“Luke”搜索结果如何与连 接到查询用户的其他节点相关的上下文信息。换言之，查询用户的用户节 点202和用于“Luke”的用户节点202通过朋友类型矢线206被连接到相 同的197个用户节点202。在具体实施方式中，搜索结果可包括多级世系 片断。多级世系片断提供关于片断中引用的用户或者概念如何可以与来自 结构化查询的查询令牌相关的上下文信息。这可响应于复杂的结构化查询 使用。作为示例而不是限制性方式，用户“A”和用户“D”在社交图谱 200中可以通过兄弟类型矢线206(表示它们是兄弟)连接。响应于用于 “显示是Acme职员的兄弟的人”的结构化查询，社交网络系统160可以 生成用于用户“A”的具有陈述“用户D的兄弟。用户D是在Acme的软 件工程师”的片断的搜索结果。该片断提供关于用户“A”搜索结果如何 与用户“D”(它们是兄弟，通过兄弟类型矢线206连接)相关，和用户“D” 如何与“Acme”(用户“D”通过就职于类型矢线206连接到“Acme”) 相关的上下文信息。尽管本公开内容描述了社交片断的具体类型，但是本 公开内容考虑了任意合适的社交片断类型。

在具体实施方式中，搜索结果可包括片断，该片断包括定制的结构化 查询。例如，这可以呈现为片断内的内联链接。一旦定制的结构化查询将 查询传输至社交网络系统160，查询用户然后可以能够点击或选择。在具 体实施方式中，定制的结构化查询可以基于相关联的搜索结果定制，使得 定制的结构化查询包括对对应于搜索结果的节点的引用(并且对其他社交 图谱元素可能的引用)。作为示例而不是限制性方式，参考图7A，用于 “Paul”的搜索结果包括读取“浏览他的照片、朋友、兴趣”的片断，其 中“照片”、“朋友”、和“兴趣”各自分别是定制的结构化查询以搜索“Paul 的照片”(即，通过加标签类型矢线206连接到“Paul”的用户节点202 的照片的概念节点204)，“Paul的朋友”，和“Paul的兴趣”(即，通过感 兴趣类型矢线206连接到“Paul”的用户节点的概念节点204)。在具体实 施方式中，定制的结构化查询可以基于相关联的搜索结果和来自最初的结 构化查询(即，用于生产搜索结果的结构化查询)的选择的节点/矢线定制。 这些定制的结构化查询则包括对对应于搜索结果的节点的引用和对来自 最初的结构化查询选择的节点和选择的矢线的引用。这些可以称为世系行 转列片断，因为它们基于来自最初的结构化查询的社交图谱元素，像世系 片断，以及对应于搜索结果的节点，因此基于搜索结果使查询行转列。作 为示例而不是限制性方式，再次参考图7A，结构化查询“目前为Facebook 工作并且喜欢骑独轮车的人”生成在结果字段710中示出的搜索结果。用 于“Tom”的搜索结果可以包括具有结构化查询“汤姆的喜欢骑独轮车的 朋友”的片断，因此引用搜索结果的用户节点202(即，“Tom”的用户节 点202)和来自最初的结构化查询的选择的节点和选择的矢线(即，通过 喜欢类型矢线206连接的用于“骑独轮车”的概念节点204)。作为另一示 例而不是限制性方式，参考图7F，结构化查询“在帕洛阿尔托，加利福 尼亚喜欢墨西哥餐馆的人”生成在结果字段710中示出的搜索结果。用于 “Sol”的搜索结果包括片断“例如Reposado，The Slanted Door和12个 其他的”，其中“Reposado”和“The Slanted Door”引用用于帕洛阿尔托 的具体墨西哥餐馆的概念节点204。类似地，对“12个其他的”的引用可 以是用于结构化查询“在帕洛阿尔托，加利福尼亚的Sol喜欢的墨西哥餐 馆”的内联链接，因此引用搜索结果的用户节点202(即，“Sol”的用户 节点202)和来自最初的结构化查询的选择的节点和选择的矢线(即，用 于“帕洛阿尔托，加利福尼亚”的概念节点204和喜欢类型矢线206)。虽 然本公开内容描述了利用定制的结构化查询生成具体片断，但是本公开内 容考虑了利用定制的结构化查询生成任意合适的片断。

在具体实施方式中，社交网络系统160可以对对应于搜索结果的一个 或多个片断(或者对应于为搜索结果的目标的节点或者资料页面的片断) 进行打分。响应于结构化查询，社交网络系统160可以识别对应于查询的 节点然后访问对应于这些识别的节点的每个的一个或多个片断。社交网络 系统160然后可以为每个搜索结果确定用于对应于搜索结果的片断的每个 的得分。当生成搜索结果时，仅具有大于片断阈值得分的得分的这些片断 可以包括在搜索结果中。例如，该得分可以是置信得分、概率、质量、排 列、另一合适类型的得分或者其任意组合。作为示例而不是限制性方式， 社交网络系统160可以确定每个片断的排列，其中仅前五个排列的片断包 括在具体搜索结果中。替代地，社交网络系统160可以对每个片断进行打 分并且包括具有以得分的排列顺序呈现的搜索结果的所有可用的片断(可 能旁路排列阈值以显示更多数量的具有搜索结果的片断)。而且，不同的 搜索结果可包括不同数目的片断。例如，第一搜索结果可以仅具有与其相 关联的两个片断并且两个片断均可能以得分的排列顺序显示，而第二搜索 结果可以具有与其相关联的九个片断，并且九个片断可以得分的排列顺序 显示。在具体实施方式中，社交网络系统160可以基于片断与结构化查询 的社交相关性确定片断的得分。引用更紧密地连接或与查询用户相关的社 交图谱元素的片断可比引用未紧密连接或者与查询用户不太相关的社交 图谱元素的片断得更高的得分。在具体实施方式中，社交网络系统160可 以基于片断与结构化查询的文本相关性确定片断的得分。具体片断的文本 相关性可以基于具体片断中的术语和术语数目如何与从查询用户接收的 文本查询匹配。在具体实施方式中，社交网络系统160可以基于与查询用 户相关联的搜索历史确定片断的得分。引用查询用户之前访问的，或者与 查询用户之前访问的节点/资料页面相关的社交图谱元素的片断可以更可 能与用户的结构化查询相关。因此，这些片断可以被给出更高的相对得分。 作为示例而不是限制性方式，如果查询用户之前搜索“我的单身女性朋 友”，那么因为查询中的查询修饰语“谁是单身”，社交网络系统160可以 确定查询用户对他搜索的人的感情状态感兴趣，将搜索具有“单身”的感 情状况的用户。因此，响应于随后的查询(例如，“就读于斯坦福大学的 Facebook工程师”，如在图7E中示出的)，社交网络系统160可以对示出 搜索结果的感情状况的片断比其他片断打更高的得分，因为查询用户在该 类型的上下文信息中的兴趣历史(因此，在图7E中示出的搜索结果可以 对示出每个搜索结果的感情状况的片断打更高的得分诸如，“在恋爱中” 或者“已婚”)。在具体实施方式中，社交网络系统160可以基于搜索的种 类确定片断的得分。可以基于内容，即搜索的主体的类型对搜索进行分类。 与被搜索的内容的类型更相关的片断可以比不太相关的片断得更高的得 分。作为示例而不是限制性方式，当搜索用户时，包括关于用户的个人信 息(例如，位置、感情状况等)的片断可以比其他类型的片断得更高的得 分，因为个人信息可以被认为与搜索其他用户的查询用户更相关。作为另 一示例而不是限制性方式，当搜索概念时，包括关于概念的社交图谱信息 (例如，订阅者/粉丝的数目、赞的数目、签到/评论的数目)的片断可以 比其他类型的片断得更高的得分，因为社交图谱信息可以被认为与搜索概 念的查询用户更相关。在具体实施方式中，社交网络系统160可基于广告 赞助者确定片断的得分。广告商(诸如，对应于具体节点的具体资料页面 的用户或者管理人员)可以赞助具体节点使得引用节点的片断可以得更高 的得分。尽管本公开内容描述了以具体方式对片断进行打分，然而本公开 内容考虑以任意合适方式对片断进行打分。

图8示出用于生成搜索结果和片断的示例性方法800。方法可从步骤 810开始，即，社交网络系统160可访问包括多个节点和连接节点的多条 矢线206的社交图谱200。节点可包括第一用户节点202和多个第二节点 (一个或者多个用户节点202、概念节点204、或者其任意组合)。在步骤 820，社交网络系统160可从第一用户接收结构化查询，结构化查询包括 对一个或多个第二节点中的一个或多个选择的节点和多条矢线中的一条 或者多条选择的矢线的引用。在步骤830，社交网络系统160可以生成对 应于结构化查询的搜索结果。每个搜索结果可以对应于多个第二节点的第 二节点。而且，每个搜索结果可以包括上下文信息的关于对应于搜索结果 的第二节点的一个或多个片断。每个搜索结果的至少一个片断包括对结构 化查询的选择的节点和选择的矢线的一个或多个引用。在适当的情况下， 具体实施方式可重复图8的方法的一个或多个步骤。尽管本公开内容描述 并且示出了图8的方法按照具体顺序发生的具体步骤，然而，本公开内容 考虑图8的按照任意合适顺序发生的方法的任意合适步骤。而且，尽管本 公开内容描述并且示出了执行图8的方法的具体步骤的具体组件、设备、 或者系统，然而，本公开内容考虑了执行图8的方法的任意合适步骤的任 意合适组件、设备、或者系统的任意合适组合。

修改结构化搜索查询

如上所述，图7A至图7G示出示例性搜索结果页面。用于生成具体 搜索结果页面的结构化查询在查询字段350中示出，并且响应于结构化查 询生成的各种搜索结果在结果字段710中示出。响应于从查询用户接收的 结构化查询，社交网络系统160可以生成可以用于细化或者行转列查询的 一个或多个查询修改。查询修改可以引用具体社交图谱元素，允许查询用 户添加或替换在结构化查询中引用的社交图谱元素。在具体实施方式中， 一个或多个查询修改可以呈现在修改字段720、建议搜索字段730、扩展 搜索字段740、或者消歧字段750中的搜索结果页面上。查询修改可以通 过添加另外的术语至查询用于细化结构化查询或者使结构化查询变狭窄。 通常，添加另外的术语至结构化查询将减少通过查询生成的搜索结果的数 目。作为示例而不是限制性方式，响应于结构化查询“我的就读于斯坦福 大学的朋友”，社交网络系统160可以生成对“我的朋友”术语的查询修 改诸如，“我的[男性/女性]朋友”以通过性别过滤搜索结果，或者“我的[单 身/已婚]朋友”以通过感情状况过滤搜索结果。查询修改还可以通过改变 查询的一个或多个术语用来行转列结构化查询或者使结构化查询变宽。作 为示例而不是限制性方式，响应于结构化查询“我的就职于Facebook的 朋友”，社交网络系统160可以生成查询修改“就职于Acme”，其可以替 换“就职于Facebook”术语，从而将查询从搜索一组用户行转列至搜索另 一组。通过向查询用户提供这些建议的查询修改，社交网络系统160可以 为用户提供强大的方式以精确地搜索它们寻找的是什么。一旦查询用户选 择查询修改，可以使用适当的语法生成新结构化查询，使得也使用自然语 言句法对新结构化查询进行渲染。社交网络系统160还可以生成可以显示 在搜索结果页面上的替代的结构化查询。这些替代的结构化查询包括以下 更多地描述的建议的查询、扩大的查询、和消歧查询。尽管本公开内容描 述了以具体方式生成查询修改，然而，本公开内容考虑以任意合适方式生 成查询修改。而且，虽然本公开内容描述了以具体方式向用户显示查询修 改，然而，本公开内容考虑以任意合适的方式向用户显示查询修改。

在具体实施方式中，社交网络系统160可生成一个或多个查询修改。 查询修改可以响应于接收第一结构化查询生成，使得查询修改可以用于修 改第一结构化查询。查询修改可以是可用于修改搜索查询的任意类型的术 语。例如，查询修改可以是文本字串、n元语法、终端/查询令牌、值、特 性、查询操作员、另一合适类型的术语，或者它们的任意组合。在具体实 施方式中，查询修改可以通过种类组织。作为示例而不是限制性方式，在 图7A中示出的修改字段720示出用于“工作单位”、“学校”、“目前居住 的城市”、“家乡”、“感情状况”、“对...感兴趣”、“朋友”、“性别”、“姓 名”和“爱好的事情”。在具体实施方式中，查询修改可以被传输到查询 用户作为搜索结果页面的部分。作为示例而不是限制性方式，在图7D、 图7E、和图7F中示出的搜索结果页面都示出在修改字段720中的下拉菜 单中显示的查询修改的列表。在这些下拉菜单中列出的查询修改可以用于 添加或替换在搜索字段350中显示的结构化查询中的术语。在具体实施方 式中，定制的查询修改可以结合预键入过程生成。而不是从一列预生成的 查询修改中选择，用户可以输入文本字串，并且预键入过程可以识别对应 于来自输入的文本字串的一种或多种n元语法的社交图谱元素。社交网络 系统160然后可以呈现一个或多个可能的匹配。作为示例而不是限制性方 式，图7E示出查询用户将字串“哈佛”输入修改字段720中的用于“学 校”种类的输入栏中。作为响应，预键入过程生成几个可能的匹配查询修 改，包括“哈佛”、“哈佛法学院”、和“哈佛西湖”等。在下拉菜单中显 示的这些列出的学校是对社交图谱200中对应于这些学校的概念节点204 的引用。尽管本公开内容描述并示出查询修改的具体种类，然而，本公开 内容考虑查询修改的任意合适的种类。

在具体实施方式中，查询修改可包括对社交图谱200中的一个或多个 修改节点或者一个或多个修改矢线的引用。修改节点或者修改矢线可以用 于添加或替换引用第一结构化查询中的节点或者矢线。查询用户然后可以 选择一个或多个这些查询修改以添加修改节点/矢线至第一结构化查询，或 者通过替换结构化查询中的节点/矢线与一个或多个修改节点/矢线。作为 示例而不是限制性方式，图7D示出通过结构化查询“我的就职于Facebook 和就职于Acme作为软件工程师的朋友”生成的示例性搜索结果页面。查 询用户可以通过也指定通过搜索查询识别的用户参加的学校想要细化搜 索。为了指定学校，查询用户可以点击“学校”下拉菜单，如在图7D中 示出的，该下拉菜单可以显示通过社交网络系统160生成的一列查询修改。 在该情况下，图7D中的下拉菜单列出学校“斯坦福大学”、“门罗阿瑟顿 高中”和“加州大学伯克利分校”等。在下拉菜单中显示的这些列出的学 校是引用社交图谱200中对应于这些学校的概念节点204。查询用户然后 可以选择这些查询修改中的一个或多个以添加引用的学校至结构化查询， 从而通过学校过滤搜索结果。响应于来自查询用户的选择，社交网络系统 160可以修改结构化查询以包括对选择的学校的引用。作为另一示例而不 是限制性方式，图7B示出通过结构化查询“我的就职于Facebook的朋友” 生成的示例性搜索结果页面。对“我的朋友”的引用对应于通过朋友类型 矢线206连接到查询用户的用户节点202，而对“Facebook”的引用对应 于用于公司“Facebook”的概念节点204。在图7B中示出的修改字段720 中示出对结构化查询中的具体节点和矢线的这些引用，其中用于“工作单 位”的种类已选择术语“Facebook”，同时用于“朋友”的种类已选择术 语“我的朋友”。然而，查询用户可以想要行转列搜索以替代在另一公司 搜索朋友。为了修改查询，查询用户可以选择“工作单位”种类以改变来 自“Facebook”对另一公司，诸如，“Acme”的引用。当查询用户选择“工 作单位”种类时，社交网络系统160可以显示已为该种类生成的一列查询 修改。响应于来自查询用户的选择，社交网络系统160则可以修改结构化 查询并且将对“Facebook”的引用替换为对“Acme”的引用(使得新的结 构化查询将是“我的就职于Acme的朋友”)，从而将搜索从一组朋友行转 列至另一组。尽管本公开内容使用以具体方式的具体查询修改进行描述， 然而，本公开内容考虑使用以任意合适方式的任意合适的查询修改。

在具体实施方式中，社交网络系统160可以响应于对一个或多个查询 修改的选择生成第二结构化查询。查询用户可以从在修改字段720中示出 的菜单选择一个或多个查询修改，例如，通过点击或选择具体查询修改。 在具体实施方式中，查询修改可以引用用于第一结构化查询的额外的节点 或者额外的矢线。在该情况下，社交网络系统160可以生成包括对来自第 一结构化查询的选择的节点和选择的矢线的引用，和在选择的查询修改中 引用的每个修改节点或者修改矢线的第二结构化查询。作为示例而不是限 制性方式，对于第一结构化查询“我的在圣何塞的朋友”，社交网络系统 160可以接收查询修改“就职于Acme”(其引用通过就职于类型矢线206 连接到用于“Acme”的概念节点204)。社交网络系统160则可以生成第 二结构化查询“我的在圣何塞就职于Acme的朋友”，第二结构化查询结 合在查询修改中引用的添加节点和额外的矢线。在具体实施方式中，查询 修改可以引用用于第一结构化查询的替代的节点或者替代的矢线。在该情 况下，社交网络系统160可以生成包括对来自第一结构化查询的选择的节 点和选择的矢线的引用，除了对替代的节点的每个引用替换对第一结构化 查询的选择的节点的引用。类似地，每个引用替代的矢线替换引用第一结 构化查询的选择矢线。作为示例而不是限制性方式，对于第一结构化查询 “我在圣何塞的朋友”，社交网络系统160可以接收查询修改“在旧金山” (其引用通过居住在类型矢线206连接到用于城市“旧金山”的概念节点 204)。社交网络系统160则可以生成第二结构化查询“我的在旧金山的朋 友”，将对来自第一结构化查询的选择的节点/矢线“在圣何塞”的引用替 换为替代的节点/矢线“在旧金山”。尽管本公开内容描述了以具体方式生 成具体修改的结构化查询，然而本公开内容考虑以任意合适方式生成任意 合适修改的结构化查询。

在具体实施方式中，社交网络系统160可以对用于第一结构化查询的 一个或多个查询修改进行打分。响应于结构化查询，社交网络系统160可 以识别可以用于修改结构化查询的一个或多个查询修改。社交网络系统 160则可以确定各个识别的查询修改的得分。当生成传输至查询用户的一 组查询修改时，仅具有大于查询修改阈值得分的得分的那些查询修改可以 包括在实际传输的该组查询修改中。例如，该得分可以是置信得分、概率、 质量、排列、另一合适类型的得分或者其任意组合。作为示例而不是限制 性方式，社交网络系统160可以确定每个查询修改的排列，其中仅前六个 排列的查询修改包括在具体搜索结果中。在具体实施方式中，社交网络系 统160可以基于查询修改与结构化查询的社交相关性确定查询修改的得 分。引用更紧密地连接或与查询用户相关的社交图谱元素的查询修改可比 引用未紧密连接或者与查询用户不太相关的社交图谱元素的查询修改得 更高的得分。在具体实施方式中，社交网络系统160可以基于对应于查询 修改的可能的搜索结果的数量确定查询修改的得分。将生成更多结果的查 询修改(即，过滤出较少的结果)可以比生成较少的结果的查询修改得更 高的得分。换言之，当用于修改为第一结构化查询时，匹配更多结果(或 更多当前结果)的查询修改可以比匹配较少的结果的查询修改得更高的得 分。作为示例而不是限制性方式，图7D示出用于修改字段720中的“学 校”种类的可能的查询修改。引用“斯坦福大学”的查询修改在建议的查 询修改的该列表中可以排列靠前，因为许多搜索结果与该限制匹配。换言 之，关于对应于结果字段710中的搜索结果的用户节点202，许多这些用 户节点202可以通过矢线206连接到用于“斯坦福大学”的概念节点204。 因此，如果对用于“斯坦福大学”的概念节点204的引用添加至在查询字 段350中示出的结构化查询，那么许多当前搜索结果将仍与结构化查询匹 配(即，被过滤出的很少)。类似地，下拉菜单中的较低排名的学校，诸 如“卡耐基梅隆大学”和“圣塔克拉拉大学”可以与较少的当前结果匹配 (即，将过滤出更多的结果)，并且因而排名较低。行转列查询修改可以 类似地进行打分。在具体实施方式中，社交网络系统160可以基于与查询 用户相关联的搜索历史确定查询修改的得分。引用查询用户之前访问的， 或者与查询用户之前访问的节点/资料页面相关的社交图谱元素的查询修 改可以更可能与用户的结构化查询相关。因此，这些查询修改可被给出相 对较高的得分。作为示例而不是限制性方式，如果查询用户之前搜索“我 在斯坦福大学的朋友”，那么社交网络系统160可以确定查询用户对连接 到用于“斯坦福大学”的概念节点204的用户节点202感兴趣。因此，响 应于随后的查询，社交网络系统160可以使引用“斯坦福大学”的查询修 改的排列比其他查询修改靠前，因为查询用户对该类型的上下文信息的兴 趣历史(因此，在图7D中示出的搜索结果可以使用于“斯坦福大学”的 查询修改排列得更靠前)。在具体实施方式中，社交网络系统160可基于 广告赞助者确定查询修改的得分。广告商(诸如，对应于具体节点的具体 资料页面的用户或者管理人员)可以赞助具体节点使得引用该节点的查询 修改可以得更高的得分。尽管本公开内容描述了以具体方式对查询修改进 行打分，然而，本公开内容考虑以任意合适方式对查询修改进行打分。

在具体实施方式中，响应于第一结构化查询，社交网络系统160可以 生成一个或多个第二结构化查询以行转列结构化查询。这些第二结构化查 询的每个可基于第一结构化查询。这些可以称为建议的查询。这些建议的 查询可以是第一结构化查询的变化，其中，建议的查询使用至少一些与第 一结构化查询相同的查询令牌。然而，为了行转列查询，来自第一结构化 查询的一个或多个查询令牌可以被替换为替代的查询令牌。换言之，社交 网络系统160可以将对来自第一结构化查询的选择的节点/矢线的一个或 多个引用替换为对替代的节点/矢线的一个或多个引用以生成一个或多个 第二结构化查询。替代的查询令牌可以通过识别如果被代入到第一结构化 查询，将产生类似的搜索结果的查询令牌确定。作为示例而不是限制性方 式，对于第一结构化查询“我的就读于斯坦福大学的朋友”，社交网络系 统160可以识别可以被代入到第一结构化查询中的一个或多个查询令牌。 例如，用于“斯坦福大学”的查询令牌可以由其他学校替换。作为另一示 例，用于“谁就读于”和“斯坦福大学”的查询令牌可以由用于“谁居住 在”和“帕洛阿尔托”的查询令牌替换。该后者示例可以产生与第一结构 化查询相同的许多搜索结果，因为居住在城市帕洛阿尔托的用户与参加学 校斯坦福大学的用户之间的高重叠，因为学校在地理上紧邻该城市(即， 在社交图谱200中，在连接到用于“斯坦福”的概念节点204的用户节点 202与用于“帕洛阿尔托”的概念节点204之间可能存在大的重叠)。还可 以基于最初的查询通过使用模板确定替代的查询令牌。作为示例而不是限 制性方式，如果第一结构化查询搜索用户，建议的查询也可以搜索用户。 类似地，如果第一结构化查询搜索照片，建议的查询也可以搜索照片。在 具体实施方式中，建议的查询可以被传输到查询用户作为搜索结果页面的 部分。作为示例而不是限制性方式，在图7B中示出的搜索结果页面示出 在建议的搜索字段730中的一些示例性建议的查询。响应于第一结构化查 询“我的就职于Facebook的朋友”，社交网络系统160生成在建议的搜索 字段730中示出的建议的结构化查询“我的喜欢Facebook的朋友的朋友” 和“我的居住在帕洛阿尔托，加利福尼亚的朋友”，等。这些建议的查询 可以基于第一结构化查询生成，其中来自第一结构化查询的一个或多个查 询令牌已被替换。尽管本公开内容描述了以具体方式生成结构化查询，然 而，本公开内容考虑了以任意合适的方式生成结构化查询。

在具体实施方式中，响应于第一结构化查询，社交网络系统160可以 生成一个或多个第二结构化查询以使结构化查询变宽。这些可以称为扩大 的查询。这些扩大的查询可以是第一结构化查询的变化，其中，扩大的查 询使用比第一结构化查询少的查询令牌，或者替换具体查询令牌以生成更 多的搜索结果。换言之，社交网络系统160可以删除对来自第一结构化查 询的选择的节点/矢线的一个或多个引用以生成一个或多个第二结构化查 询。类似地，社交网络系统160可以将对来自第一结构化查询的选择的节 点/矢线的一个或多个引用替换为对替代的节点/矢线的一个或多个引用以 生成一个或多个第二结构化查询。在该情况下，可以通过识别如果代入第 一结构化查询，将产生比最初的查询令牌更多的搜索结果的查询令牌确定 替代的查询令牌。在具体实施方式中，当对应于第一结构化查询的搜索结 果低于搜索结果的阈值数目时可以生成扩大的结构化查询。具有太多限 制，或者使用与许多社交图谱实体不相配的查询令牌的结构化查询可能产 生很少或者没有结果。当结构化查询产生过少的结果时，其可对提供用于 如何修改该查询以生成另外的结果的建议有用处。社交网络系统160可以 分析第一结构化查询并且提供用于如何修改查询使得其产生更多结果的 提议。搜索结果的阈值数目可以是任意合适的结果数目，并且可以通过社 交网络系统160确定或者是用户定义的。在具体实施方式中，社交网络系 统160可以生成一个或多个第二结构化查询，第二结构化查询包括对来自 第一结构化查询的零个以上选择的节点和零个以上选择的矢线的引用，其 中，每个第二结构化查询包括与第一结构化查询相比至少少一个的对选择 的节点或者选择的矢线的引用。作为示例而不是限制性方式，参考图7A， 响应于第一结构化查询“目前为Facebook工作并且喜欢骑独轮车的人”， 社交网络系统160在扩展搜索字段740中生成扩大的查询“喜欢骑独轮车 的人”和“目前Facebook员工”。这些扩大的查询可以基于第一结构化查 询生成，其中，已去除来自第一结构化查询的一个或多个查询令牌(即， 已分别去除对“Facebook”和“独轮车”的引用)。通过去除来自第一结 构化查询的限制，更多用户应该满足查询并且因此这些查询应该生成更多 搜索结果。在具体实施方式中，社交网络系统160可以生成一个或多个包 括对来自第一结构化查询的零个以上选择的节点和零个以上选择的矢线 的引用的第二结构化查询，其中，每个第二结构化查询包括将对第一结构 化查询的选择的节点或者选择的矢线的至少一个引用分别替换为替代的 节点或者替代的矢线。作为示例而不是限制性方式，再次参考图7A，社 交网络系统160生成扩大的查询“对骑独轮车感兴趣的Facebook过去录 用的人”和“对骑独轮车感兴趣的Facebook曾经录用的人”。这些扩大的 查询可以基于第一结构化查询生成，其中“目前为...工作”查询令牌已分 别被“过去录用”查询令牌和“曾经录用”查询令牌替换，从而使用不同 的时间表过滤搜索结果(其可以使来自就职于类型矢线206的可以满足该 查询的连接矢线的类型扩展至还包括就职于类型矢线206)。在具体实施方 式中，扩大的查询可以被传输到查询用户作为搜索结果页面的部分。作为 示例而不是限制性方式，在图7A中示出的搜索结果页面示出在扩展的搜 索字段740中的以上已论述的一些示例性扩大的查询。尽管本公开内容描 述了以具体方式生成具体扩大的查询，然而本公开内容考虑以任意合适方 式生成任意合适扩大的查询。

在具体实施方式中，响应于第一结构化查询，社交网络系统160可以 生成一个或多个第二结构化查询以使结构化查询消歧。这些可以称为消歧 查询。这些消歧查询可以是第一结构化查询的变化，其中消歧查询使用来 自第一结构化查询的一些查询令牌，但是还可以将一些查询令牌替换为替 代的查询令牌。可以发生某些节点可以对应于来自查询用户的来自非结构 化文本查询的相同的n元语法(例如，用于“斯坦福”的n元语法可以对 应于用于任一学校“斯坦福大学”或者城市“斯坦福，加利福尼亚”的概 念节点204)。当引用的矢线类型或者引用的节点之间的关系在结构化查询 中不清楚时，消歧也可以有帮助。社交网络系统160可以确定具体结构化 查询是歧义的，由于查询用户可以不同的方式解释结构化查询的自然语言 句法。因此，当选择具体结构化查询时，社交网络系统160可以生成出乎 意料的或者不是查询用户寻找的搜索结果。在这些情形中，社交网络系统 160可以提供结构化查询如何被解析和其如何识别显示的搜索结果的解 释。另外，社交网络系统160可以提供最初的查询的变化以帮助查询用户 找到他或她寻找的。在具体实施方式中，消歧查询可以被传输到查询用户 作为搜索结果页面的部分。作为示例而不是限制性方式，在图7G中示出 的搜索结果页面示出在消歧搜索字段750中显示的示例性消歧查询。响应 于第一结构化查询“我的来自田纳西州的朋友的照片”，社交网络系统160 生成消歧查询“我的朋友在田纳西州的照片”。社交网络系统160还提供 其如何解析第一结构化查询的解释，陈述“这些结果示出属于你的来自田 纳西州的朋友的照片”。换言之，社交网络系统160解析第一结构化查询 以识别对应于通过加标签类型矢线206连接到用户节点202的照片的概念 节点204，并且其中这些用户节点202通过居住在或者来自类型矢线206 连接到用于“田纳西州”的概念节点204。与此相反，建议的消歧查询将 识别对应于通过拍摄于类型矢线206连接到用于“田纳西州”的概念节点 204的照片的概念节点204，其中用于照片的概念节点204也连接到查询 用户的朋友的用户节点202。尽管本公开内容描述了以具体方式生成具体 消歧查询，然而本公开内容考虑以任意合适方式生成任意合适消歧查询。

图9示出了用于修改结构化搜索查询的示例性方法900。方法可从步 骤910开始，其中，社交网络系统160可访问包括多个节点和连接节点的 多条矢线206的社交图谱200。节点可包括第一用户节点202和多个第二 节点(一个或者多个用户节点202、概念节点204、或者其任意组合)。在 步骤920，社交网络系统160可从第一用户接收结构化查询，结构化查询 包括对多个第二节点中的一个或多个选择的节点和多条矢线中的一条或 多条选择的矢线的引用。在步骤930，社交网络系统160可以生成用于第 一结构化查询的一个或多个查询修改。每个查询修改可以包括对多个第二 节点中的一个或多个修改节点或多条矢线中的一条或多条修改的矢线的 引用。在适当的情况下，具体实施方式可重复图9中的方法的一个或多个 步骤。尽管本公开内容描述并且示出了图9中以具体顺序发生的方法的具 体步骤，然而，本公开内容考虑了图9中以任意合适顺序发生的方法的任 意合适步骤。而且，尽管本公开内容描述并且示出了执行图9中的方法的 具体步骤的具体组件、设备、或者系统，然而，本公开内容考虑了执行图 9中的方法的任意合适步骤的任意合适组件、设备、或者系统的任意合适 组合。

系统和方法

图10示出了示例性计算机系统1000。在具体实施方式中，一个或多 个计算机系统1000执行本文描述或示出的一种或多种方法的一个或多个 步骤。在具体实施方式中，一个或多个计算机系统1000提供本文描述或 示出的功能。在具体实施方式中，在一个或多个计算机系统1000中运行 的软件进行本文描述或示出的一种或多种方法的一个或多个步骤，或者提 供本文描述或示出的功能。具体实施方式包括一个或多个计算机系统1000 的一个或多个部分。此处，在适当情况下，对计算机系统的引用可包含计 算设备，反之亦然。此外，在适当情况下，对计算机系统的引用可包括一 个或多个计算机系统。

本公开内容考虑任意合适数量的计算机系统1000。本公开内容考虑采 用任意合适的物理形式的计算机系统1000。作为示例而不是限制的方式， 计算机系统1000可以是嵌入式计算机系统、片上系统(SOC)、单板计算 机系统(SBC)(诸如，电脑模组(COM)或者系统模组(SOM))、桌面 计算机系统、膝上型或者笔记本计算机系统、交互式自助服务机、主机、 计算机系统网络、移动电话、个人数字助理(PDA)、服务器、平板计算 机系统、或者这些中两种或者多种的组合。在适当情况下，计算机系统1000 可包括一个或多个计算机系统1000；为整体式或者分布式；跨多个地点；跨 多台机器；跨多个数据中心；或者驻留在可包括一个或者多个网络中的一个 或多个云组件的云中。在适当情况下，一个或多个计算机系统1000可执 行本文所描述或者示出的一种或者多种方法的一个或多个步骤，而基本没 有空间和时间限制。作为示例而不是限制的方式，一个或多个计算机系统 1000可实时地或以批量模式执行本文所描述或者示出的一种或多种方法 的一个或多个步骤。在适当情况下，一个或多个计算机系统1000可在不 同时间或者在不同位置执行本文所描述或者示出的一种或多种方法的一 个或多个步骤。

在具体实施方式中，计算机系统1000包括处理器1002、内存1004、 存储器1006、输入/输出(I/O)接口1008、通信接口1010和总线1012。 尽管本公开内容描述并示出了具有按照具体布置的具体数量的具体组件 的具体计算机系统，但是本公开内容考虑具有按照任意合适布置的任意合 适数量的任意合适组件的任意合适的计算机系统。

在具体实施方式中，处理器1002包括用于执行诸如装配计算机程序 的指令的硬件。作为示例而不是限制的方式，为了执行指令，处理器1002 可从内部寄存器、内部缓存、内存1004或者存储器1006中重新得到(或 者取来)指令；解码并且执行他们；然后向内部寄存器、内部缓存、内存 1004或者存储器1006写入一个或多个结果。在具体实施方式中，处理器 1002可包括用于数据、指令或地址的一个或多个内部缓存。在适当的情况 下，本公开内容考虑包括任意合适数量的任意合适的内部缓存的处理器 1002。作为示例而不是限制的方式，处理器1002可包括一个或多个指令 缓存、一个或多个数据缓存以及一个或多个转换后备缓冲器(TLB)。在 指令缓存中的指令可以是在内存1004或存储器1006中的指令的复制，并 且指令缓存可以加速处理器1002对那些指令的检索。数据缓存中的数据 可能是内存1004或者存储器1006中的用于在处理器1002执行来操作的 指令的数据；在处理器1002执行的用于在处理器1002执行的后继指令访 问的或者用于写入内存1004或者存储器1006的先前指令的结果；或者其 他合适的数据的副本。数据缓存可加速处理器1002的读取或写入操作。 TLB可以加速处理器1002的虚拟地址转换。在具体实施方式中，处理器 1002可包括用于数据、指令或地址的一个或多个内部寄存器。在适当的情 况下，本公开内容考虑包括任意合适数量的任意合适的内部寄存器的处理 器1002。在适当的情况下，处理器1002可包括一个或多个算术逻辑单元 (ALU)；可以是多核处理器；或者包括一个或多个处理器1002。尽管本 公开内容描述和示出了具体处理器，但是本公开内容考虑任意合适的处理 器。

在具体实施方式中，内存1004包括用于储存处理器1002执行的指令 或处理器1002操作的数据的主存储器。作为示例而不是限制的方式，计 算机系统1000可将指令从存储器1006或另一源(诸如，另一计算机系统 1000)加载至内存1004。然后，处理器1002可将指令从内存1004加载至 内部寄存器或内部缓存。为了执行该指令，处理器1002可从内部寄存器 或者内部缓存检索指令并且将它们进行解码。在指令的执行之中或之后， 处理器1002可将一个或多个结果(其可以是中间结果或最终结果)写入 到内部寄存器或内部缓存。然后，处理器1002可将那些结果中的一个或 多个写入到内存1004。在具体实施方式中，处理器1002仅在一个或多个 内部寄存器或内部缓存或内存1004(与存储器1006相反的位置或其他位 置)中执行指令，并且仅在一个或多个内部寄存器或内部缓存或内存1004 (与存储器1006相反的位置或其他位置)中操作数据。一个或多个内存 总线(每个可包括地址总线和数据总线)可将处理器1002耦接至内存 1004。如下所述，总线1012可包括一个或多个内存总线。在具体实施方 式中，一个或多个内存管理单元(MMU)位于处理器1002与内存1004 之间，并且促进由处理器1002要求的对内存1004的访问。在具体实施方 式中，内存1004包括随机存取存储器(RAM)。在适当情况下，该RAM 可以是易失性存储器，在适当情况下，该RAM可以是动态RAM(DRAM) 或静态RAM(SRAM)。此外，在适当情况下，该RAM可以是单端口或 多端口的RAM。本公开内容考虑任意合适的RAM。在适当情况下，存储 器1004可包括一个或多个存储器1004。尽管本公开内容描述和示出了具 体的内存，但是本公开内容考虑任意合适的内存。

在具体实施方式中，存储器1006包括用于数据或指令的大容量存储 器。作为示例而不是限制的方式，存储器1006可包括硬盘驱动(HDD)、 软盘驱动、闪存、光盘、磁光盘、磁带或通用串行总线(USB)驱动或者 它们的两种或多种的组合。在适当情况下，存储器1006可包括可移除的 或者不可移除的(或固定的)介质。在适当情况下，存储器1006可以在 计算机系统1000的内部或外部。在具体实施方式中，存储器1006是非易 失性的固态存储器。在具体实施方式中，存储器1006包括只读存储器 (ROM)。在适当情况下，该ROM可以是掩码编程ROM、可编程ROM (PROM)、可擦PROM(EPROM)、电可擦PROM(EEPROM)、电可改 写ROM(EAROM)或闪存或这些的两个或更多的组合。本公开内容考虑 采用任意合适物理形式的大容量存储器1006。在适当情况下，存储器1006 可包括促进处理器1002与存储器1006之间通信的一个或多存储器控制单 元。在合适的情况下，存储器1006可包括一个或多个存储器1006。尽管 本公开内容描述和示出了具体的存储器，但是本公开内容考虑任意合适的 存储器。

在具体实施方式中，I/O接口1008包括为计算机系统1000与一个或 多个I/O设备之间的通信提供一个或多个接口的硬件、软件或这两者。在 适当情况下，计算机系统1000可包括一个或者多个这种I/O设备。这些 I/O设备的一个或多个可启用个人与计算机系统1000之间的通信。作为示 例而不是限制性方式，I/O设备可包括键盘、按键、麦克风、监控器、鼠 标、打印机、扫描仪、扬声器、照相机、触控笔、平板、触摸屏、追踪球、 摄影机、其他合适的I/O设备或它们中两个或更多的组合。I/O设备可包 括一个或多个传感器。本公开内容考虑任意合适的I/O设备和它们的任意 合适的I/O接口1008。在适当的情况下，I/O接口1008可包括使处理器 1002能够驱动这些I/O设备中的一个或多个的一个或多个设备或软件驱动 器。在适当的情况下，I/O接口1008可包括一个或多个I/O接口1008。尽 管本公开内容描述和示出了具体的I/O接口，但是本公开内容考虑任意合 适的I/O接口。

在具体实施方式中，通信接口1010包括提供用于在计算机系统1000 与一个或多个其他计算机系统1000或者一个或多个网络之间进行通信(诸 如，例如，基于数据包的通信)的一个或多个接口的硬件、软件或者两者。 作为示例而不是限制性方式，通信接口1010可包括用于与以太网或其他 基于导线网络通信的网络接口控制器(NIC)或网络适配器，或用于与无 线网络(诸如WI-FI网络)通信的无线NIC(WNIC)或无线适配器。本 公开内容考虑任意合适的网络和它的任意合适的通信接口1010。作为示例 而不是限制性方式，计算机系统1000可与自组织网络、个人局域网(PAN)、 局域网络(LAN)、广域网络(WAN)、城域网(MAN)或互联网的一个 或多个部分或它们的两个或更多的组合通信。这些网络中的一个或多个的 一个或多个部分可以是有线或无线的。作为示例，计算机系统1000可以 与无线PAN(WPAN)(如，例如，蓝牙WPAN)、WI-FI网络、WI-MAX 网络、蜂窝电话网络(如，例如，全球移动通信系统(GSM)网络)或其 他合适的无线网络或这些的两个或更多的组合通信。在适当情况下，计算 机系统1000可包括用于这些网络中的任意一个的任意合适的通信接口 1010。在适当的情况下，通信接口1010可包括一个或多个通信接口1010。 尽管本公开内容描述和示出了具体的通信接口，但是本公开内容考虑任意 合适的通信接口。

在具体实施方式中，总线1012包括将计算机系统1000的组件彼此耦 接的硬件、软件或者硬件和软件。作为示例而不是限制性方式，总线1012 可包括图形加速端口(AGP)或者其他图形总线、增强型产业标准体系 (EISA)总线、前端总线(FSB)、超传输(HT)互连、工业标准结构(ISA) 总线、无线带宽互连、低脚位(LPC)总线、内存总线、微通道结构(MCA) 总线、外部设备互连(PCI)总线、PCI Express(PCIe)总线、串行高级 技术附件(SATA)总线、视频电子标准协会局部(VLB)总线、或者另 一合适的总线或者这些的两种或多种的组合。在适当的情况下，总线1012 可包括一个或多个总线1012。尽管本公开内容描述和示出了具体的总线， 然而本公开内容考虑任意合适的总线或者互连。

本文中，在适当的情况下，计算机可读非易失性存储介质或者媒介可 包括一个或多个基于半导体的或者其他集成电路(IC)(诸如，现场可编 程门阵列(FPGA)或者专用集成电路(ASIC))、硬盘驱动器(HDD)、混 合硬盘驱动器(HHD)、光盘、光碟驱动器(ODD)、磁光盘、磁光驱动 器、软盘、软盘驱动器(FDD)、磁带、固态驱动器(SSD)、RAM驱动 器、安全数码卡或者驱动器、任意其他合适的计算机可读非易失性存储媒 介、或者这些的两种或多种的任意合适的组合。在适当的情况下，计算机 可读非易失性存储媒介可以是易失的、非易失的，或易失和非易失的组合。

杂项

此处，除非另有明确表示或通过上下文另有表示，否则“或”是包括 性的而不是排除性的。因此，在本文中，除非另有明确表示或通过上下文 的其他表示，否则“A或B”意味着“A、B、或这两者”。此外，除非另 有其他明确表示或通过上下文的其他表示，否则“和”是两者结合及多个。 因此，在本文中，除非另有其他明确表示或通过上下文的其他表示，否则 “A和B”意味着“结合地或分别地A和B”。

本公开内容的范围包括本领域技术人员应当理解的对本文中描述或 示出的示例性实施方式的所有改变、替代、变化、变更以及修改。本公开 内容的范围并不限于本文中描述或示出的示例性实施方式。此外，尽管本 公开内容将本文中各个实施方式描述并且示出为包括具体组件、元件、功 能、操作或步骤，但是本领域普通技术人员应当理解的是，这些实施方式 中的任意一个可包括本文中任意地方描述或示出的任意组件、元件、功能、 操作或步骤的任意组合或排列。此外，无论是否它或该具体功能被激活、 打开或者解锁，只要该装置、系统或组件是如此适应、布置、能够、配置、 启动、可操作、或者操作的，所附权利要求涉及的装置或者系统或者装置 或者系统的组件适用于、布置为、能够、被配置为、启动、能操作以、或 者操作执行包括装置、系统、组件的具体功能。