The goal of the expert search task is nding knowledgeable persons within the enterprise. In this paper we focus on its distinctions from the other information retrieval tasks. We review the existing approaches and propose a new term weighting scheme which is based on analysis of communication patterns between people. The e ectiveness of the proposed approach is evaluated on a collection of e-mails from an organization of approximately 1500 people. Results show that it is possible to take into account communication structure in the process of term weighting, e ectively combining communication-based and document-based approaches to expert nding.
The problem of locating desired information or source of knowlege has been faced by almost everyone, and sometimes nding a right person may be even more valuable than nding the right documents. In large enterprises such as companies and goverment agencies it may become a task of major importance.
For example, according to Yimam-Seid&Kobsa [
It may be also important to identify users or groups of users who are more knowlegeable than the others. In a big enterprise it may help discover new ideas, the most valuable employees and sources of innovations.
An expert search system is designed to help with these tasks. In contrast with classical information retrieval where documents are retrieved, given a query, the system has to return a ranked list of person names in response.
Most approaches to expert nding tend to copy standard information
retrieval methods, such as Vector Space Model [
Existing methods can be divided into communication-based, that take into
account the communication patterns between users, and content-based, which
focus strictly on the documents content. An essential notion in content-based
methods is term signi cance. It is used to estimate the generality or speci city
of a term and evaluate how important is a word to a document, collection or
corpus. The process of calculating term signi cance is called term weighting and
the most common approach to term weighting is the tf-idf measure and it's
variations [
The problem of existing term weighting schemes as well as other contentbased methods is that they don't take into account communication patterns between users. They may be combined with communication-based approaches sequentially, but there is no existing method that allows communication structure to a ect the term's weight. Developing such method could be a signi cant contribution to the domain.
In this paper we analyse the speci cs of the task, review the existing approaches to expert nding and term weighting and propose a new weighting scheme developed speci cally for expertise evaluation. 2
As it has been mentioned earlier, the expert search task has di erent properties from the standart information retrieval task. The standard IR task was developed for analysing web pages and text collections such as online libraries. An expert search task needs to deal with forums, social networks, blogs and corporate emails.
We consider the following properties of the expert search task the most important: { In business environment size of the available corpora is limited by the company lifespan, therefore number of documents is relatively small. Same counts for social networks. { Corpora may contain information that normal text collections don't, like authorship or communication patterns. { Communications between authors are not the same as hyperlinks. The possibility to relate every document to its author creates a hierarchical structure, which is absent in the standard IR task.
Naturally, di erent data organization demands alternative approaches to its processing, that take into account additional features and information they provide. Existing but rare approaches to standart IR such as time marks may also prove useful. Further investigation of the impact of some of this information to extracting data from business corpora is required. 3 3.1
The most direct approach to expert nding is adapting Vector Space Model for
the task. VSM, one of the most successful solutions to IR, has proved to be highly
e ective for many types of documents. VSM represents queries and documents as
vectors in an n-dimensional information space. Then it systematically compares
each document vector with the query vector to nd the documents nearest to
the query. To adapt VSM for referral systems, each person is represented with
a vector based on a "document" consisting of all messages they sent to the
user. A person vector contains weights for each term in the query based on how
frequently the term was used by the sender in his or her email messages. An
example of this approach has been described in [
Let Pi be the person vector for colleague pi. This vector contains the computed weights for all terms in the sender's email that also occurs in the query vector. Adaptation of TF-IDF metrics and variations are the most common for calculating the weights.
wik =
tfik log(N=nk) pPn t=1[(tfik) log(N=nk]2 : (1)
Here, N = number of colleagues of the user, nk = number of colleagues who have used term k, tfik = term frequency; number of times colleague pi has used term k.
It can be separated into the term frequency factor (tf) and the inverse document frequency factor (idf, collection factor).
The rst gives a measure of the importance of the term t within the particular context, document or user pro le. The simplest case is the occurrence count of a term in a document. The more a term is encountered in a certain context, the more it contributes to the meaning of the context
Inverse document frequency factor diminishes the weight of terms that occur very frequently in the collection and increases the weight of terms that occur rarely. It is a measure of the general importance of the term (obtained by dividing the total number of documents by the number of documents containing the term, and then taking the logarithm of that quotient).
Variations of this scheme include term relevance weight (i.e. probabilistic
term inverse frequency) and inverse term frequency, a good overview can be
found in [
The calculation of the query vector, Qj , can be taken directly from
information retrieval methods with computed weights for each term in the query
vector < wj1; wj2; :::wjn >. Several di erent query vectors has been proposed,
for example, by Salton and Buckley [
After person vectors have been calculated for each sender, the similarity between the query vector and a person vector can be calculated as the cosine of the angle between those vectors. Using this sort of similarity measure, the agent will return to the user a list of potential experts ranked in decreasing order of computed similarity values upon a query. The term weights can be normalized, so the similarity is between 0 and 1. It is convenient to think of this value as the likelihood or con dence that a person will be able to answer the query of the user. 3.2
The ranking scheme and it's variations described above don't take into account
link structure or communication patterns. A rather more popular approach for
expert nding are schemes that focus speci cally on those properties, which has
proven to be more e ective [
One of the most famous is PageRank. In this approach the obtained ranking is the principal eigenvector of the adjacency matrix of the digraph in which edges correspond to links (messages) between users. This approach turns out to be virtually idenctical to the well-known PageRank algorithm for ranking web pages, the only di erence being that in PageRank low-weight edges are added between all nodes in both directions.
The simplest is the successor model, where messages are viewed as directed edges pointed from greater to lesser expertise. All the people 'downstream' from a given node are considered of lesser expertise. This one measure of expertise is simply the count of such people (nodes) Another is positional power function (PPF), where the ranks(riji = 1::n) satisfy the following system of equations: ri =
X 1
n j 2 Si (rj + 1) : (3)
An adaptation of HITS algorithm, a precursor to PageRank was also
proposed in [
Neither of those pays attention to term weighting, focusing only on communication patterns. 4
The goal of our work was is to investigate the impact of communication pattern analysis to expertise evaluation in business corpora and the possibility of using this information during term weighting.
In case of expert nding the main task of term weighting is to divide generic terms from professional vocabulary. Selecting rare terms doesn't always work, as well as the TF-IDF scheme, since rare terms may be generic as well. However, signi cance of the term may correlate with the patterns of communicaion between people who use it. Generic terms tend to come up randomly in documents of any domain created by authors of all kinds of occupation and level of professional expertise, while professional terminology is mostly used between experts and people asking for a consultation, and experts are normally few and tend to interact with each other. Those people should form a tight cluster, while generic term users would be scattered around the enterprise with relatively small amount of connections.
The main idea of our approach is to calculate the number of clusters that people form for every term in the corpora and to compare it to the number of clusters that would be formed if the links between users were distributed randomly.
The proposed method was analyzed on a collection of e-mails from an organization of approximately 1500 people consisting of 1270000 messages. 5
For every term, information about the number of occurrences, number of people using the term and messages id was included in the index. For every message senders and receivers were known.
For every n = 3::50 all terms that were used by n people was selected. Then for every term the number of clusters k its users were forming was computed, and nally for every pair (n; k) the number of terms was measured.
Then a random distribution of messages has been modelled.
For every n = 3::50 200 terms were randomly selected from the table, then, according to number of term users n1 and number of term encounters n2, n1 people were randomly selected from the list of users and liked ("sending messages") to n2 any other users on the list. Uniform distribution was used for the probability of creating link with another user. As a result an alternative index was created, then numbers of all (n; k) pairs from this index were computed according to the algorithm described above. 6
The random distribution pictures show that the number of terms, users of which form a single cluster, is vanishingly small. It is highly improbable for such terms to occur by chance.
At the same time, pictures of the factual distribution contain a much higher number of "single cluster" terms, and the distribution graph itself is atter. Therefore it can be concluded that those terms do not appear at random and may share some common properties.
It also appeared that probability of term being professional instead of generic corresponds with the number of clusters. Terms with smaller k values tend to be more signi cant.
Taking all these things into account, we nd it reasonable to assume that number of clusters can be used as an important indicator of term signi cance.
This leads to a following weighting scheme: (4) (5) wij = p pr : p = Nnk , pr = Nnk;r , where p is the probability of n users forming k clusters for
Nn Nn;r factual distributuion, pr the probability of it for random distributuion, Nnk and Nnk;r are the number of terms, users of which form k clusters, in factual and random distribution accordingly, Nn and Nn;r are the total number of terms that are used by n people.
If wij > 1 term is considered a professional one and if wij < 1 the term is considered general.
A simpler, though less accurate scheme is wij =
k kmostprobable :
Here if the number of users is n and they form k clusters, kmostprobable is the value that has the highest number of (n; k) pairs in random distribution.
Those schemes can be used by itself or in a combination with TF-IDF as an additional factor.
Precise evaluation is currently unachievable due to the small amount of annotated data available - there are no corpora focusing on the term level. The direction of our future work is building a full expert search system based on this scheme. It will allow to evaluate the approach using standart expert search corpora, annotated on text level, such as, for example, the TREC 2005 task. 7
In this paper we have shown that it is possible to make analysis of communication patterns a part of a term weighting scheme, and have suggested an example of such scheme. We have also focused on the distinctions between expert nding and standard IR task.
The proposed approach allows to take into account the speci cs of the expert search task. It also allows to adapt the existing approaches (such as vector space models, for example) for expert nding more e ectively.
For further investigation, we are focusing on proper evaluation of the scheme, combining it with other term weighting schemes. and improving it by exploring the impact of other properties like graph density.