| Whether in real life,or in a virtual network,when an user needs to find the valuable objects from a large amount of candidates,if purely relying on artificially checking,analysing and identifying one by one,the workload is very huge.Then comes our ranking algorithm,it can find out those valuable objects in a very short period of time,for example,the web search ranking and the influential person ranking.According to the kinds of ranking objects,the present ranking algorithms can be categorized into the general-object ranking and person-object ranking.Besides,according to the patterns of ranking,each kind object ranking algorithms can be further classified into direct ranking algorithm and merging ranking algorithm.Direct ranking algorithm attains a ranking results through directly accessing the data objects.Merging ranking algorithm obtains its final ranking result through merging multiple ranking lists into a comprehensive one.Although the study of different objects ranking caused wide attention of researchers,but in different application scenarios,there are still some research spaces,the research tasks of this paper are aimed to tackle the following problems:in view of the general objects:Direct ranking algorithms for the direct search application,due to the ineffective use of some structural characteristics of graph,their ranking efficiency is affected;Merging algorithms for the federated search application,due to the neglecting to list credibility,the quality of the lists merging is degraded;in view of the person objects:Direct ranking algorithms for the hot people found application,due to the ignoring of the effect of some key information on the graph,their ranking quality is affected;Merging algorithms for the voting application,because of not distinguishing the credibility between different rankings info,the further quality improvement of the voting list merging is affected.In order to achieve the purpose of improving the efficiency and quality of ranking,we need to do many performance optimizations of present ranking algorithms from different angles.In this paper,the optimizations on ranking quality or on ranking efficiency are all called optimizations on ranking performance.In order to achieve optimizations on ranking performance,in addition to the need to make full use of a variety of features and information in graph,we also need to comprehensively measure different types of credibility.So about the ranking of the general-objects,for the direct search and federated search application scenarios,two approaches are proposed respectively in this paper:the strongly connected component based efficient page rank approach and lists credibility based lists merging approach;about the ranking of the general-objects,for the hot persons found and voting application scenarios,other two approaches are proposed respectively in this paper:ranking the influence of persons by integrating multiple factors effects and rank-info reliability based voting lists merging approach.From the above,the main work of this paper can be generalized into the following four parts:(1)Structural Feature based PR Ranking Approach.In this part,based on a special sub-graph:SCC(Strongly Connected Component),analyzing and exploiting the features and properties of SCCs exhibited in the Page Rank computation,we propose a SCC-based efficient optimization algorithm.During the process of the proposition,some strict theorems are proposed to guarantee the correctness of the accordingly algorithm.At the mean time of analyzing the general patterns,we also discussed the optimization process under some specific situation and thus improved the efficiency of the algorithm from multiple angles.(2)List Reliability based Lists Merging Approach.In this part,we aim to merge multiple lists returned by multiple retrieval systems into a more reliable comprehensive one.Due to the difference of the ground data and ranking algorithms,the reliability of lists returned by different retrieval systems is usually different too.So during the lists merging process,we should pay more attention on those lists of high reliability.Based on this thought,in this part,we aim to figure out the reliability of each list without supervision during the lists merging process,and then make the lists of high reliability play a more important role on the comprehensive list computation,and thus improve the quality of lists merging.(3)Person Influence Ranking by Integrating Multiple Factors.Different from the previous ranking algorithms,in this part,besides the relations between nodes,the information that reflecting nodes importance are also considered for ranking computation,which makes the ranking results of one person node not only are influenced by their social ability which are reflected by the external relations(the recognition by others),but also are influenced by their business ability supported by its property information,i.e.,makes the ranking results reflect the comprehensive abilities of persons and thus improves the quality of the ranking results effectively.Besides,during the process of business ability measurements,we also considered the time fading effect which is induced by people' subjective forgetting issue,and thus can get the comprehensive importance ranking under some specific time point more precisely.(4)Rank-Info Reliability based Voting Lists Merging Approach.In this part,for a special kind of lists:voting lists,we proposed the algorithms which merge the multiple voting lists into a comprehensive one.For the merging of voting lists,due to the different cultural background and ability of voters,the reliabilities of the voting lists given by them are different too;besides,even in a same voting list,the reliability of the ranking info about different candidates can also be different due to the voter's different"acquaintance" with the candidates.The algorithm proposed in this part not only measures the reliability of voters,but also measures the "acquaintance" with candidates,and then based on these data gets the reliability of each rank-info.During the final merging step,lets the rank-info of high reliability play a more important role,and reaching the purpose of the quality improvement of lists merging.In conclusion,this paper aims to provide users with more satisfactory ranking service,so we need to do many optimizations of present ranking algorithms from different angles.On the aspect of ranking objects,this paper not only analyzes the ranking of general-objects,it also discusses the ranking of person-objects.On the aspect of application scenarios,for the four scenarios:direct search,federated search,hot people found and voting,this paper respectively analyzed the ranking problem needed to be solved in them,and proposed the corresponding algorithms.On the aspect of the way of ranking,direct ranking and lists merging are studied.In short,the algorithms proposed in this paper improved the efficiency and quality of the objects ranking effectively from different angles. |
PDF Full Text Request