随机过程在网页排序中的应用研究

网页排序算法是搜索引擎的核心技术，也是数学与信息科学交叉的重点研究课题之一，具有极大的创新性和实用背景。对于各类排序算法的设计已有许多研究结果，但到目前为止仍然没有对于算法的理论分析。自2008年我们提出的基于随机过程的排序算法发表后，立刻引起学术界和工业界的高度关注，均认为随机过程理论是目前最合理的研究工具。此后，我们又提出设计了一系列的随机算法来分析对比，并获得了更多深入的理论结果。本课题的研究目标就是在排序理论方面形成一个完备的框架，将目前已有的各类代表算法囊括其中，并在这个平台上进行对比分析和进一步衍化。本项目拟形成一套基于马氏骨架过程的排序方法，给出用户在网页上浏览行为的精确描述，在不同的网络数据结构上设计更有效更合理的网页重要性和相关性排序算法，并尝试分析排序的本质、对比排序与分类等其他方法的异同。

网页排序算法是搜索引擎的核心技术，也是数学与信息科学交叉的重点研究课题之一，具有极大的创新性和实用背景。对于各类排序算法的设计已有许多研究结果，但到目前为止仍然没有对于算法的理论分析。自2008年我们提出的基于随机过程的排序算法发表后，立刻引起学术界和工业界的高度关注，均认为随机过程理论是目前最有效的研究工具之一。此后，我们又提出设计了一系列的随机算法来分析对比，并获得了更多深入的理论结果。本课题的研究目标就是在排序理论方面形成一个完备的框架，将目前已有的各类代表算法囊括其中，并在这个平台上进行对比分析和进一步衍化。..通过三年的项目执行，本项目（一）首次定义了名为网络马氏骨架过程的新随机过程，并验证离散时间马氏过程、连续时间马氏过程、半马氏过程和镜面半马氏过程均可以涵盖在网络马氏骨架过程的框架下；（二）建立了基于网络马氏骨架过程的排序理论框架，并在该框架上统一分析了目前所提出的各类网页重要性排序算法；（三）在不同的网络数据结构上设计更有效更合理的网页重要性排序算法，例如建立了镜面半马氏过程排序模型，为手机网络设计了MobileRank算法；（四）给出了用户在网络上浏览网页行为的精确描述，并提出了更合理的用户浏览网页过程的特征；（五）详细分析了网络马氏骨架过程的理论属性，包括1）网络马氏骨架过程的时齐性，2）时齐网络马氏骨架过程的遍历理论，3）时齐网络马氏骨架过程的重构理论，4）网络马氏骨架过程与跳过程的关系。