KR101230687B1 - Link-based spam detection - Google Patents

Abstract

A computer-implemented method is provided for ranking search hits in a search result set. The method receives a question from a user and generates a list of hits related to the question, wherein each of the hits has a relevance to the question, the hits have one or more rising link documents that indicate the hits, and the rising link Documents influence the relevance of hits to the question. The method associates a measure with the hits indicating the number of ascending link documents each pointing to. The method compares the threshold and the measure, processes the list of hits to form a modified list based in part on the comparisons, and sends the modified list to the user.

Description

Link-based Spam Detection {LINK-BASED SPAM DETECTION}

The present invention relates generally to a search system and in particular to a search system for ranking search hits in the final set.

Searching is useful when the entire corpus cannot be absorbed and the exact pointer to the targeted items does not exist or is not possible. In general, retrieval is the process of formulating or accepting a search query, determining a set of matching documents from a corpus of documents, and returning the set or some subset of the set if the set is too large. In certain embodiments that do not limit the disclosure, consider searching for a set of hyperlinked documents called "Web." The corpus then contains many searchable items called pages, or more generally documents. The search engine typically identifies documents from the corpus that match the search query using a pre-generated index prior to receipt of the search query. "Matching" can mean many things and a search query can take many forms. In general, a search query is a string containing one or more words or terms and a matching occurs when the document includes one or more words or terms (or both) from the search query string. Each matching document is called a hit and a set of hits is called a result set or search results. The corpus may be a database or other data structure or unorganized data. Documents are often web pages.

A typical index of web pages contains billions of entries, so a general search has a result set that includes millions of pages. Clearly, in such situations, the search engine should include an additional result set such that it is reasonable to return to the interrogator (typically a human computer user, but need not be the case). One way of suppressing the set is to provide the search results in an order with the assumption that the user reads or uses only the upper, smaller number of hits that appear higher in the sequential search results.

Because of this assumption, many web page authors want their pages to appear higher in sequential search results. The search engine selects and returns only the highest quality depending on the various characteristics of the relevant pages. Since the top positions (high ranking) in the query results list provide advantages for the business, the authors of certain web pages attempt to unfairly boost the ranking of the pages. Pages with artificially boosted rankings are called "web spam" pages and collectively known as "web spam".

There are various technologies related to web spam. One of them is to properly create a web page to be selected by many questions. This is accomplished by increasing pages with large amounts of terms that are not related to the core content and are rendered in small or invisible fonts. The increase causes the page to be more exposed (ie, potentially related to more questions), but does not truly improve the relevance to any particular question. In this regard, spam authors use different techniques: spam authors use pages based on the observation that pages cited more often by others are generally considered desirable (higher relevance) by search engines. Add many incoming links, so-called inlinks. In fact, the higher values make it difficult to distinguish high quality pages that are cited by many others from web spam with many inlinks.

The identification of future demotions in web spam pages and search results lists is important for maintaining or improving the quality of answers formed by search engines. Therefore, web spam detection is a necessary task for search engines. Human editors are primarily used to identify web spam by examining multiple pages provided in the search engine index, but this is often difficult to implement.

Therefore, there is a need for an improved search process that overcomes web spam and provides search results that better match the user's wishes, rather than matching the document author's manipulations.

Embodiments of the present invention provide systems and methods for processing search results that include rank hits that form a search result set. Hits are ranked using the effective mass, which is a spam farm size measure for a particular page, and other parameters.

In one embodiment, the present invention provides a computer-implemented method of ranking search hits in a search result set. The computer-implemented method includes receiving a question from a user and generating a list of hits associated with the question, where each hit is associated with the question, and the hits have one or more boosted linked documents for the hits. However, boosting linked documents affect the relevance of hits to the question. The method is then associated with a measurement for each of at least one subset of hits, the method indicating a number of linked documents that each point to each of the at least one subset of hits and artificially inflating the relevance of the hits. . The method then compares the threshold with a measure indicating the size of the spam farm indicating the hits, processes the list of hits to form a modified list based in part on the comparison, and uses the modified list as a user. Send to.

In one aspect, the measurement is a combination of the first and second measurements. The first measure for a hit indicates the link popularity of the hits, and the second measure is a measure of the likelihood that the hit is a reliable document.

In another aspect, the second measure forms a seed set of trusted documents that are links to documents, assigns a trust value to each of the documents in the seed set, and indicates the trust value by the documents linking. Generated by passing to each of the linked documents and assigning an assigned trust value to each of the linked documents.

In another aspect, a seed set of trusted documents determines an outlink measure that indicates the number of respective outlinks of the documents for each of the plurality of documents, ranks the plurality of documents using the outlink measure, Form a set of modified documents by identifying the highest ranked documents in the set, evaluating the quality of the highest ranked documents, removing documents that are considered inappropriate from the highest ranked documents, and creating the modified maintenance set. It is formed by forming a seed set to be used.

The following detailed description, in conjunction with the accompanying drawings, will provide a better understanding of the nature and advantages of the present invention.

1 is an exemplary block diagram of an information retrieval and communication network that may be used to practice embodiments of the present invention.

2 is an exemplary block diagram of an information retrieval and communication network in accordance with an embodiment of the present invention.

3A-B are exemplary diagrams of simple spam farms.

Unless defined, all technical and scientific terms used herein have the meaning commonly understood by one of ordinary skill in the art to which this invention belongs. As used herein, the following terms are defined as follows.

PageRank is a type of well known algorithm for assigning numerical weights to hyperlinked documents (or web pages or web sites) indexed by a search engine. Page Rank uses the link information to assign global importance scores to documents on the web. The page ranking process is patented and described in US Pat. No. 6,285,999. The page rank of a document is a measure of the link based popularity of the document on the web.

TrustRank is a link analysis technique related to page rank. Trust ranking is a way to separate reliable, quality pages on the web from web spam. The trust ranking is based on the possibility that top documents on the web rarely link to spam. Confidence rank includes two steps: seed selection and score delivery. The confidence rank of a document is a measure of the likelihood that the document is a reliable (ie, no spam) document.

A link or hyperlink generally refers to a clickable document on a web page that leads to another page, another site, or another portion of the same page. Thus, clickable content is referred to as a link to another page / site / part of the same page. Spiders use links to crawl from one page to the next when indexing Web sites.

Inbound link or inlink / outbound link or outlink. When Site A links to Site B, Site A is an outbound link and Site B is an inbound link. Inbound links are counted to determine link popularity.

The web, or the world wide web ("WWW", or simply "web") is an information space in which items of interest called resources are identified by global identifiers called so-called uniform resource identifiers (URIs). The term web is often used as a synonym for the Internet; However, the web is actually a service that runs on the Internet.

Web pages or web pages are generally in the HTML / XHTML format (file extensions are typically htm or html) and the World Wide Web with hypertext links that enable navigation from one page or section to another. This is called the page or file of. Webpages often use associated graphic files to provide a drawing, which may also be clickable links. Web pages are displayed using a web browser and are often designed to use applets (subprograms rather than operating within the page) that provide motion, graphics, dialog, and sound.

A web site is called a collection of web pages stored in a single folder or related subfolders of a web server. Web sites typically include a front page called index.htm or index.html.

A web host is a business that provides file maintenance for server space, web services, and web sites controlled by individuals or companies that do not have their own web servers. Many Internet Service Providers (ISPs) allow subscribers a small amount of server space for hosting personal web pages.

Spam is generally unwanted documents or emails of commercial nature that are distributed in large quantities.

Web spam is called spam pages on the web. The act of generating web spam is called web spamming. Web spamming is the act of misleading search engines in order to provide some higher ranking documents that are worth receiving. Spam pages on the web are the result of some form of spamming. One form of spamming is link spamming.

Spam pages are web documents that receive illegal boosts in ranking scores and therefore may appear in top search results and attempt to mislead search engines.

Link spamming often refers to the creation of interconnected spam documents and the formation of groups called so-called spam farms, which are formed so that multiple boosting documents increase the link based importance ranking of one or a few target pages.

A spam farm refers to a group of interlinked spam pages created to boost the link based importance score (eg, page rank scores) of specific target pages.

summary

Embodiments of the present invention relate to methods and systems for the detection of link based spam. Search results formed in response to the search query are processed to determine the amount of valid hits. The effective hit amount is a measure of the size of the spam farm generated to indicate hits and artificially boost the relative importance of the hits. The method and system according to embodiments of the present invention use the number of valid hits and represent the hits, the effective amount of hits being artificially boosted by link based spam. The determination of the effective amount for a given web document is based on a combination of techniques that partially evaluate the mismatch between link based popularity (eg, page rank) and trust value (eg, trust rank) of a given web document. Techniques for determining the effective amount of a given web document are described in detail later.

Network running

1 illustrates a general overview of an information retrieval and communication network 10 that includes one or more client systems 20 _1-N that may be used to practice embodiments of the present invention. In the computer network 10, the client system (s) 20 _{1 -N} connect to the Internet 40, or other communication network (eg, any local area network (LAN) or wide area network (WAN) connection). via is coupled to any number of server systems (50 ₁ to 50 _N). As will be described herein, client system (s) 20 _{1 -N} may be any server systems 50 ₁ for accessing, receiving, retrieving, and displaying other information such as, for example, media content and web pages. To 50 _N ) in accordance with the invention.

Some elements of the system shown in FIG. 1 include conventional well known elements that do not need to be described in detail herein. For example, client system 20 may interface directly or indirectly to a desktop personal computer, workstation, laptop, personal digital assistant (PDA), cell phone, or any WAP-enabled device or the Internet. It can include any other computing device. Client system 20 typically includes Microsoft's Internet Explorer ^TM browser, Netscape Navigator ^TM browser, Mozilla ^TM browser, Opera ^TM. Browsers, Apple's Safari ^TM or cell phones, PDAs or other wireless devices operate browsing programs such as WAP-enabled browsers, or the like, allowing users of client systems 20 _1-N to access server systems via the Internet 40. the information and makes it possible to access the page, processing and viewing in use from the (50 ₁ to 50 _N). Client system 20 is typically a server system (50 ₁ to 50 _N) or a display (e.g., monitor screen, LCD display, etc.) in conjunction with pages, forms and other information provided by the other server, One or more user interface devices 22, such as a keyboard, mouse, touch screen, pen, or the like, for interfacing with a graphical user interface (GUI) provided by an upper browser. The present invention is suitable for use on the Internet regarding a particular globally relevant set of networks. However, it is understood that other networks may be used instead of or in addition to the Internet, such as intranets, extranets, virtual private networks (VPNs), non-TCP / IP based networks, any LAN or WAN or the like.

According to one embodiment, client system 20 and all components include computer software operation using a central processing unit such as an Intel Pentium ^™ processor, AMD Athlon ^™ processor, Apple Power PC, or the like or multiprocessors. An operator that can be configured using an application. Computer software for operating and configuring client system 20 for communicating, processing, and displaying data and media content as described herein is preferably downloaded and stored on a hard disk, but the entire program code, or portions thereof, Can be stored on any other well-known volatile or nonvolatile memory media or device, such as ROM or RAM, or can store program code such as compact disk (CD) media, digital versatile disk (DVD) media, floppy disks, and the like. May be provided on any medium. In addition, the entire program code, or portions thereof, may utilize any communication medium and protocols (eg, TCP / IP, HTTP, HTTPS, Ethernet, or other conventional medium and protocols) to provide software source over the Internet. For example, from one of the server systems 50 ₁ to 50 _N to be transmitted and downloaded to the client system 20, or to any other network connection (e.g., extranet, VPN, LAN or other conventional networks). Can be transmitted through

Computer code for carrying out aspects of the present invention may be implemented in C, C ++, HTML, XML, Java, JavaScript, etc., code, or any other suitable scripting language (eg, VBScript), or client system 20. It should be appreciated that it may be any suitable programmable language that may be executed or compiled on the client system 20, or the systems 20 _{1 -N} . In some embodiments, the code is downloaded to the client system 20 and the necessary code is executed by the server, or code already provided to the client system 20 is executed.

Search system

2 illustrates another information retrieval and communication network 110 for communicating media content in accordance with one embodiment of the present invention. As shown, network 110 includes client system 120, one or more content server systems 150, and search server system 160. In network 110, client system 120 is communicatively coupled to server systems 150 and 160 via the Internet 140 or other communications network. As discussed above, client system 120 and its components are configured to communicate with server systems 150 and 160 and other server systems via the Internet 140 or other communications networks.

1. Client system

According to one embodiment, a client application (represented as module 125) running on client system 120 communicates with server systems 150 and 160 and processes the client to process and display data content received from the server systems. Instructions for controlling the system 120 and its components. The client application 125 may be a remote server system (eg, a server system, although the client application module 125 may be stored on any software storage medium, such as a floppy disk, CD, DVD, etc., as discussed above). 150, server system 160, or other remote server system) to a client system 120 from a software source. For example, in one aspect, the client application module 125 may, for example, manipulate and render data of various objects, frames, and windows via the Internet 140, for example, with embedded JavaScript or ActiveX controls. May be provided to the client system 120 of an HTML wrapper that includes various controls such as the above.

In addition, the client application module 125 may include a search module 126 for processing search requests and search result data, such as text and data content of text and data frames such as browser windows and dialog boxes and active windows. Various software modules for processing data and media content, such as a user interface module 127 for rendering them and an application interface module 128 for interfacing and communicating with various applications executing on the client 120. . Examples of various applications running on client system 120, preferably configured by application interface module 128 to interface, include various email applications, instance messaging (IM) applications, browser applications, document management applications, and the like. And so on. In addition, the interface module 127 may include a browser, such as a default browser or other browser configured on the client system 120.

2. Search Server System

According to one embodiment, search server system 160 is configured to provide search result data and media content to client system 120. Client server system 150 is configured to provide data and media content, such as web pages, to client system 120 in response to selected links, for example, in search results pages provided by search server system 160. . In some variations, search server system 160 returns the content as well as or instead of links and / or other references to the content.

In one embodiment, search server system 160 cites pages representing indexed pages, etc., links to pages, and various page indices 170 in which data resides. Page indexes may be generated by various collection techniques including automatic web crawlers, spiders, etc. as well as automatic or semi-automatic classification algorithms and interfaces for classifying and ranking web pages in a hierarchy. These techniques may be implemented in search server system 160 or in an independent system (not shown) that creates page index 170 and makes it available to search server system 160.

Search server system 160 is configured to provide data in response to various search requests received from client systems, such as search module 126. For example, search server system 160 may be web based on a given question (e.g., based on logical relevance measured by occurrence patterns of search terms in the question; context identifiers; page sponsorship; etc.). Search-related algorithms for processing and ranking pages.

Link-based Spam Detection

As shown in FIG. 2, search server system 160 operates in conjunction with a link based spam detector 180 that returns a modified search list and provides its output (results, suggestions, media content, etc.). Where the web spam pages were demoted or removed from the list. Search server system 160 is configured to operate a search engine in accordance with embodiments of the present invention. The search engine consists of three parts: one or more spiders 162, a database 163 and tools / applications 167. Spiders 162 crawl from the Internet collection information; The database 163 contains other information as well as information collected by spiders; And tools / applications 167 include applications such as search tool 166 used by users to search through a database. Database 167 includes page index 170 used by a search tool. In addition, the search engine according to an embodiment of the present invention includes a spam detector 180. The spam detector 180 executes various algorithms described below and stores web spam measurements 181 for the pages of the page index 170. As noted above, spam detector 180 in accordance with embodiments of the present invention evaluates a measure that corresponds to the amount of valid hits and operates in conjunction with search tool 166 and page index 170 and the amount of valid hits. This will demote artificially boosted hits by link-based spam. Determination of the effective amount for a given web document relies on a combination of techniques that partially evaluate the mismatch between link based popularity (eg page rank) and trust value (eg trust rank) of a given web document. In one embodiment, the web spam detector 180 processes all the pages of the page index 170 and calculates the web spam measurement 181 in the database 163 to calculate the web spam measure 181 for the pages of the index. Save it. The measure 181 is independent of the search query that causes the document to be included in the search results.

The determination of the effective amount of spam farm by the spam detector 180 for a given web document is in part dependent on the link based popularity (eg page rank) and trust value (eg trust rank) of the given web document. Depends on the primary rating. The determination of the trust value of a given web document depends in part on how far away a given page is from the initial seed set of web documents known to be trustworthy (ie, no spam documents). Accordingly, the search engine according to embodiments of the present invention includes a seed set generator 184 that operates in conjunction with the page index 170 to form an initial seed set 185 of reliable web documents. The operation of the spam detector 180 forming the web spam measure 181 and the seed set generator 184 forming the seed set 185 are described in detail later.

Spam Farm, Page rank  And trust ranking

In this section, concepts of spam farm, inlink page ranking (commonly referred to as "page ranking"), and trust ranking are described. A spam farm is a set of artificially generated pages that point to spam target pages in order to boost importance. Confidence ranking (“trust ranking”) is a form of page ranking with specific teleportations (ie jumps) to a subset of high quality pages. Using the techniques described herein, the search engine can automatically detect bad pages (web spam pages) and boost its importance through the creation of artificial spam farms (collections of citation pages) more specifically. Discover web spam pages created for In certain embodiments, page ranking processing with uniform teleportation and confidence ranking processing is performed and the results are compared as part of a check of "spamability" of a page or "spamability" of a collection of pages. In addition, a new method of configuring inputs for confidence ranking processing is described below.

One aspect of the invention relates to the identification of spam pages (at least in part) based on analysis of the surrounding hyperlink structure. In particular, a new method of estimating spam farm sizes is used. Since no spam pages rarely point to spam, the specific rights distribution of the trust ranking causes a certain degree of separation between the non-spam pages and the spam pages; High quality no spam web pages are expected to have the highest scores assigned by the trust ranking.

Confidence ranking relates to a well-known web analytics algorithm, page ranking, which assigns numerical scores to each web page according to the scores of the other pages indicated. Page ranking uses teleportation techniques: A certain amount of total score is delivered to some or all pages according to a so-called teleportation distribution, which is generally a uniform distribution. Instead of using uniform teleportation distribution, the trust ranking provides teleportation only to trusted (no spam) web pages (ie, a so-called "seed set"). This results in distributing scores from the actual seed set to other pages.

The following descriptions cite web pages. However, logic, execution, and algorithms may be defined by (1) the web of sites (logical groups of web content / pages and other forms of web documents related to one permission), (2) some definitions of graph edges between hosts. By a web (hostrank) of hosts (e.g., if the two hosts with at least one page connected by a hyperlink, the host graph has two links, or other checks) It is equally applicable to a collection of links associated with weights reflecting the web proximity of sites represented, (3) any other web page graph set, and / or (4) strength of referrals.

Spam farm

A spam farm is a set of artificially generated pages (or optionally hosts) that point to spam target pages to boost importance. 3A-3B are exemplary diagrams showing two simple spam farms.

3A shows that the spam farm has all m pages pointing to the target spam page s. The process for obtaining a good estimate of spam farm size is described below. For every page i, the number M _i is calculated, where the number M _i is called the “effective amount” of the page. For web spam pages, M uses the page as a good estimate of the size of the spam spam boosting the page.

For a simple spam farm, the effective amount is close to m. For more complex farms, for example in the spam farm shown in FIG. 3B, the effective amount M is used as an indicator, and a high M value indicates a spam farm. Although the above description cites web pages, it should be appreciated that the concepts may be applied to groups of pages, hosts and the like.

Page Rank and Trust Rank

The concept of page rank is used when analyzing web pages. Of the many possible definitions of page rank, the linear system definition of the following page rank is used:

x = cT ^T x + (1-c) v (equation 1)

In equation 1:

T is a transition matrix where elements are T _ij = 1 / outdeg (i) if there is a link (i → j) from page i to page j, otherwise zero. Where outdeg (i) is the number of outlinks on page i used as a standardization factor to form a matrix T probability,

c is the teleportation constant selected from the range (0.7-0.9),

x = (x _i ) is the permission vector, where index i is all running on n pages, i = 1: n (n is the number of web pages),

v = v (v _i ) is a teleportation vector assumed to be a probability distribution, and 0≤v _i ≤1, v ₁ + ... + v _n = 1.

Iterative methods for solving Equation 1 are known. Equation 1 has the advantage of defining a linear permission vector in relation to the teleportation vector.

For page rank, p is a permission vector that provides a solution of equation 1 corresponding to a single teleportation (ie, when v _i = 1 / n). For confidence ranks, t is a privilege vector that provides a solution of equation 1 corresponding to a particular teleportation (i.e. v such that k elements of v are nonzero and the remainder is zero, and nonzero elements are corresponding indices in a reliable set). (i)).

Evaluation of effective amount

The effective amount of the web page is used as an indicator to help the web page determine the spam page.

Evaluation composition

For any potential spam page (s), among any web page (i),

p _s -t _s = b _s ^rise + b.p _s ^leak + (1-c) / n (Equation 2) is mathematically shown, where right term 1 of the equation is a supporting spam farm (the farm is no spam). Pages are empty or non-existent), resulting in a boost reaching the page, and paragraph 2 is due to permission leaks from non-spam pages that are sometimes mispointed to spam pages. This leak is shown in FIGS. 3A-B as dashed arrows representing various accidental hyperlinks from the rest of the web to a given page. For the spam page s, the first term is very dominant because it forms a page rank of s which is highly motivated to the spam generators creating the spam farm. About a simple farm,

p _s ^rise = m · c (1-c) / n (equation 3)

Similar expressions are valid for farms of other structures. For example, for a farm with back links,

p _s ^rise = m c (1-c) / (1-c ² ) n (equation 4)

Under conditions where p _s ^leakage << p _s ^rise (Equation 5), a good estimate for the size m of a simple spam farm is constructed from equations (2) and (3) as follows.

M _s = n (p _s -t _s ) / c (1-c) (equation 6)

Equation 6 defines the effective amount M _i that can be calculated for any web page i. As mentioned above, if i is a spam page boosted by a simple spam farm, M _i approaches the actual farm size (m), and for other farms, the actual farm size as shown by equation 4 Differs from one constant. The difference is not important in terms of the fact that the actual spam farms are rather large (eg millions of boost pages are generated negatively).

For the no spam page, M _i will be some number that is not large in terms of absolute terms or p _i . Link-based spam detection in accordance with embodiments of the present invention finds this and does not name the page as a potential web spam page based on M _i as an indicator.

Spam detection processing

The following example process is used to detect link based spam. The process is very simple and effective and aims to find the pages with the highest effective amount. However, the effective amount provides an excellent approximation to spam size if equation (5) is satisfied, so that the popularity from reliable web pages is much smaller than the link based popularity of the page due to artificial boost by spam pages. Ensures the popularity of links based on the page. Under the condition of equation 5, the spam detection process can distinguish between legitimately popular pages and pages that are made popular by the linked spam farm. The technique according to embodiments of the present invention ensures that the condition of equation 5 is met. This is done in the following step (C), which is an algorithm parameter η> 1 uses as the threshold. It can be seen that large proportions of C correspond to pages satisfying equation (5). In total, an exemplary process is as follows:

A. For all pages (hosts, etc.), i of the list (eg, the list of hits associated with the question, or page index) finds the effective amount M _i according to equation 6.

B. Maintain or identify pages (i) sorted and top part of sorted list in decreasing order of M _i . Optionally, the entire list can be maintained even if it does not require too many resources, so maintaining a low M _i is less effective. Such identification and / or maintenance may be performed at any stage. The selection processing portion relates to selecting pages with both high M _i and high M _i / P _i .

C. Find ratios M _i / P _i for all pages (i) kept in the list.

D. Delete M _i / P _i <η from pages i.

E. Retained pages constitute spam.

In the experiment, the detected spam pages are actually found to be spam (by human judgment) in most cases. This means that negative potential rates can be lowered using these techniques.

Seed set

The process described above is in accordance with the so-called confidence rank, i.e. the solution of equation 1, with a particular teleportation distribution associated with the seed set. The seed set is a set of k high quality pages known as no spam. Aspects of embodiments of the present invention relate to the discovery of suitable seeds in trusted value (ie, no spam) pages or sites. One way to identify a seed set of trusted web pages is to recommend specific web pages based on human editorial judgment. However, human evaluation is expensive and time consuming. Another technique for semi-automatically configuring the seed set, while maintaining the option of manually selecting the seed set as a viable alternative, is described below.

Seed selection processing is in accordance with the opinion that seed pages must have two important characteristics, i.e., a number of other pages must be reached repeatedly by following outlinks on the facing web pages starting from the seed pages, And 2) seed pages are of very high quality, so that the chance of encountering a link from no spam to spam should be minimized.

In order to ensure the first feature, a ranking of all pages (ie page index pages) is formed. For this purpose, the following linear system shown by equation 7 is used.

y = cU ^T y + (1-c) v (equation 7)

In this system,

U is the reverse transition if elements j _ij = 1 / indeg (i) if the link j → i, or zero otherwise. Where indeg (i) is the number of inlinks to page i, which is used as a normalization factor to form the matrix U probability,

c is usually the teleportation constant chosen from the range (0.7-0.9),

y = (y _i ) is a privilege vector, where index i is operated on all n pages, i = 1: n,

-V = v ( _i ), assumed to be a probability distribution, is a teleportation vector, where 0≤v _i ≤1, v ₁ + ... + v _n = 1.

It is noted that the system described by Equation 7 is similar to Equation 1, except that Equation 7 uses a reverse transition matrix U instead of the normal disparity matrix T. The reverse transition matrix corresponds to a web graph with the directionality of the reversed links. To do this, the solution to equation 7 with uniform teleportation is called inverse page rank. Inverse page rank is a measure of how many webs can be reached from one page along the outlinks on the page.

To ensure the second feature of the seed pages, the pages with the highest inverse page rank are further processed by the human editor. The human editor chooses that the candidates (pages that provide high coverage as measured by inverse page rank) are actually high quality no spam pages. The pages selected by the human editor are included in the seed set as described above and used in the confidence rank calculation.

An example seed set configuration process is summarized as follows:

A. For all pages (hosts, etc.), i finds the inverse page rank y _i according to equation

B. Maintain the top rank of pages (i) sorted and sorted list in decreasing rank of y _i , or otherwise identify and maintain the set of highest ranked pages

C. Use human editor (s) to assess the quality of pages maintained on the list

D. Deleting list pages recognized by editor (s) as inappropriate

E. Retained pages constitute seed set.

Experiments show that the resulting seed set is suitable for confidence rank calculations and spam detection based on both estimates derived from page rank and confidence rank.

Embodiments described herein may cite particular web sites, links, and other techniques when the world wide web (or a subset of the world wide web) is used as a search corpus. The systems and processes described herein can be provided for use in another search corpus (such as an electronic database or document repository) and the results are links or citations to the content as well as to locations where the content can be found. It must be understood.

Thus, although the invention has been described in connection with specific embodiments, it is recognized that the invention is intended to cover all modifications and equivalents within the scope of the following claims.

Claims (10)

A method of ranking search hits in a set of search results, the method being performed by a computing system, Receiving a question from a user; Generating a list of hits related to the question, each hit of the list of hits having a relevance to the question, wherein at least one hit is indicated by a link in a boosting document, A link in a boosting document artificially increases the relevance of the at least one hit to the question; Determining a first measure for the at least one hit, the first measure being a link-based popularity measure for the at least one hit; Determining a second measure for the at least one hit, the second measure being a confidence measure for the at least one hit, indicating the likelihood that the at least one hit is a reputable document; Generating a metric for the at least one hit based at least in part on the discrepancy between the first and second measurements, the metric being equal to the at least one hit for the question. Representing a plurality of boosting documents comprising links to the at least one hit, artificially increasing relevance; Comparing a threshold with a value based at least in part on the metric; Processing the list of hits to form a modified list, wherein the processing comprises, in response to determining that the value based at least in part on the metric is greater than the threshold: Excluding the at least one hit from the modified list; or, Demoting the at least one hit in the modified list Further performing any one of; And Sending the modified list to the user in response to the question And ranking the search hits. The method of claim 1, wherein generating the metric is performed prior to receiving the question. The method of claim 1, wherein determining the second measurement comprises: Forming a seed set of good documents, wherein the seed set of good documents includes links to other documents; Assigning a confidence value to each of the documents in the seed set; Propagating the confidence value to each of a plurality of documents pointed to by at least one of the documents in the seed set; And Assigning a prorated confidence value to each of a plurality of documents indicated by at least one of the documents in the seed set. The method of claim 3, Forming the seed set comprises: determining, for each of the second plurality of documents, an outlink metric, each representing a plurality of outlinks included in each of the second plurality of documents; Ranking the second plurality of documents using the outlink metric; Identifying a set of highest ranked documents in the second plurality of documents; Receiving an input identifying one or more documents from the set of highest ranked documents to be included in the seed set; Forming a modified set of highest ranked documents based on the input; And Forming a seed set using the modified set of highest ranked documents. The method of claim 1, Determining the first measurement, determining the second measurement, and generating the metric are performed for each hit in the list of hits, The method comprises: After generating the metric for each hit in the list of hits, sort the list of hits based on the metrics generated for the hits in the list of hits. Generating an ordered list; Identifying a top portion of the sorted list, wherein hits in the top are associated with higher metrics than hits that are not in the top; For each hit in the top of the sorted list, determining whether to classify the hit as spam based on a ratio of the metric to the first measure. How to rank hits. A computer readable storage medium having stored thereon instructions for ranking search hits in a search result set, comprising: The instructions are performed by a computing system, The instructions are Receiving a question from a user; Generating a list of hits related to the question, wherein each hit of the list of hits is relevant to the question, at least one hit is indicated by a link in a boosting document, and the link in the boosting document is Artificially increasing the relevance of the at least one hit to the question; Determining a first measure for the at least one hit, the first measure being a link-based popularity measure for the at least one hit; Determining a second measure for the at least one hit, the second measure being a measure of reliability for the at least one hit, indicating the likelihood that the at least one hit is a good document; Generating a metric for the at least one hit based at least in part on the discrepancy between the first and second measurements, the metric being equal to the at least one hit for the question. Representing a plurality of boosting documents comprising links to the at least one hit, artificially increasing relevance; Comparing a threshold with a value based at least in part on the metric; Processing the list of hits to form a modified list, wherein the processing comprises, in response to determining that the value based at least in part on the metric is greater than the threshold; Excluding the at least one hit from the modified list; or, Demoting the at least one hit in the modified list Further performing any one of; And Sending the modified list to the user in response to the question Computer-readable storage medium comprising instructions for performing the operation. 7. The computer readable storage medium of claim 6, wherein generating the metric is performed prior to receiving the question. The method of claim 6, wherein determining the second measurement comprises: Forming a seed set of good documents, wherein the seed set of good documents includes links to other documents; Assigning a confidence value to each of the documents in the seed set; Passing the confidence value to each of a plurality of documents pointed to by at least one of the documents in the seed set; And Assigning a credit value assigned to each of a plurality of documents pointed to by at least one of the documents in the seed set. 9. The method of claim 8, Forming the seed set comprises: determining, for each of the second plurality of documents, an outlink metric, each representing a plurality of outlinks included in each of the second plurality of documents; Ranking the second plurality of documents using the outlink metric; Identifying a set of highest ranked documents in the second plurality of documents; Receiving an input identifying one or more documents from the set of highest ranked documents to be included in the seed set; Forming a modified set of highest ranked documents based on the input; And And forming the seed set using the modified set of highest ranked documents. The method of claim 6, Determining the first measurement, determining the second measurement, and generating the metric are performed for each hit in the list of hits, The instructions are After generating the metric for each hit in the list of hits, the list of hits is sorted based on the metrics generated for the hits in the list of hits, Generating a list; Identifying a top of the sorted list, wherein hits in the top are associated with higher metrics than hits that are not in the top; For each hit in the top of the sorted list, determining whether to classify the hit as spam based on the ratio of the metric to the first measure, Computer-readable storage media.

Images