Modelling selectional preferences in a lexical hierarchy

This paper describes Bayesian selectional preference models that incorporate knowledge from a lexical hierarchy such as WordNet. Inspired by previous work on modelling with WordNet, these approaches are based either on "cutting" the hierarchy at an appropriate level of generalisation or on a "walking" model that selects a path from the root to a leaf. In an evaluation comparing against human plausibility judgements, we show that the models presented here outperform previously proposed comparable WordNet-based models, are competitive with state-of-the-art selectional preference models and are particularly well-suited to estimating plausibility for items that were not seen in training.

Introduction
The concept of selectional preference captures the intuitive fact that predicates in language have a better semantic "fit" for certain arguments than others. For example, the direct object argument slot of the verb eat is more plausibly filled by a type of food (I ate a pizza) than by a type of vehicle (I ate a car), while the subject slot of the verb laugh is more plausibly filled by a person than by a vegetable. Human language users' knowledge about selectional preferences has been implicated in analyses of metaphor processing (Wilks, 1978) and in psycholinguistic studies of comprehension (Rayner et al., 2004). In Natural Language Processing, automatically acquired preference models have been shown to aid a number of tasks, including semantic role labelling (Zapirain et al., 2009), parsing (Zhou et al., 2011) and lexical disambiguation (Thater et al., 2010;Ó Séaghdha and Korhonen, 2011).
It is tempting to assume that with a large enough corpus, preference learning reduces to a simple language modelling task that can be solved by counting predicate-argument co-occurrences. Indeed, Keller and Lapata (2003) show that relatively good performance at plausibility estimation can be attained by submitting queries to a Web search engine. However, there are many scenarios where this approach is insufficient: for languages and language domains where Web-scale data is unavailable, for predicate types (e.g., inference rules or semantic roles) that cannot be retrieved by keyword search and for applications where accurate models of rarer words are required.Ó Séaghdha (2010) shows that the Webbased approach is reliably outperformed by more complex models trained on smaller corpora for less frequent predicate-argument combinations. Models that induce a level of semantic representation, such as probabilistic latent variable models, have a further advantage in that they can provide rich structured information for downstream tasks such as lexical disambiguation (Ó Séaghdha and Korhonen, 2011) and semantic relation mining (Yao et al., 2011).
Recent research has investigated the potential of Bayesian probabilistic models such as Latent Dirichlet Allocation (LDA) for modelling selectional preferences (Ó Séaghdha, 2010;Ritter et al., 2010;Reisinger and Mooney, 2011). These models are flexible and robust, yielding superior performance compared to previous approaches. In this paper we present a preliminary study of analogous models that make use of a lexical hierarchy (in our case the WordNet hierarchy). We describe two broad classes of probabilistic models over WordNet and how they can be implemented in a Bayesian framework. The two main potential advantages of incorporating WordNet information are: (a) improved predictions about rare and out-of-vocabulary arguments; (b) the ability to perform syntactic word sense disambiguation with a principled probabilistic model and without the need for an additional step that heuristically maps latent variables onto Word-Net senses. Focussing here on (a), we demonstrate that our models attain better performance than previously-proposed WordNet-based methods on a plausibility estimation task and are particularly wellsuited to estimating plausibility for arguments that were not seen in training and for which LDA cannot make useful predictions.

Background and Related Work
The WordNet lexical hierarchy (Fellbaum, 1998) is one of the most-used resources in NLP, finding many applications in both the definition of tasks (e.g. the SENSEVAL/SemEval word sense disambiguation tasks) and in the construction of systems. The idea of using WordNet to define selectional preferences was first implemented by Resnik (1993), who proposed a measure of associational strength between a semantic class s and a predicate p corresponding to a relation type r: where η is a normalisation term. This measure captures the degree to which the probability of seeing s given the predicate p differs from the prior probability of s. Given that we are often interested in the preference of p for a word w rather than a class and words generally map onto multiple classes, Resnik suggests calculating A(s, p, r) for all classes that could potentially be expressed by w and predicting the maximal value.
Cut-based models assume that modelling the selectional preference of a predicate involves finding the right "level of generalisation" in the WordNet hierarchy. For example, the direct object slot of the verb eat can be associated with the subhierarchy rooted at the synset food#n#1, as all hyponyms of that synset are assumed to be edible and the immediate hypernym of the synset, substance#n#1, is too general given that many substances are rarely eaten. 1 This leads to the notion of "cutting" the hierarchy at one or more positions (Li and Abe, 1998). The modelling task then becomes that of finding the cuts that are maximally general without overgeneralising. Li and Abe (1998) propose a model in which the appropriate cut c is selected according to the Minimum Description Length principle; this principle explicitly accounts for the trade-off between generalisation and accuracy by minimising a sum of model description length and data description length. The probability of a predicate p taking as its argument an synset s is modelled as: where c s,p,r is the portion of the cut learned for p that dominates s. The distribution P (s|c s,p,r ) is held to be uniform over all synsets dominated by c s,p,r , while P (c|p) is given by a maximum likelihood estimate. Clark and Weir (2002) present a model that, while not explicitly described as cut-based, likewise seeks to find the right level of generalisation for an observation. In this case, the hypernym at which to "cut" is chosen by a chi-squared test: if the aggregate preference of p for classes in the subhierarchy rooted at c differs significantly from the individual preferences of p for the immediate children of c, the hierarchy is cut below c. The probability of p taking a synset s as its argument is given by: P cw (s|p, r) = P (p|c s,p,r , r) P (s|r) P (p|r) s ∈S P (p|c s ,p,r , r) P (s |r) where c s,p,r is the root node of the subhierarchy containing s that was selected for p. An alternative approach to modelling with Word-Net uses its hierarchical structure to define a Markov model with transitions from senses to senses and from senses to words. The intuition here is that each observation is generated by a "walk" from the root of the hierarchy to a leaf node and emitting the word corresponding to the leaf. Abney and Light (1999) proposed such a model for selectional preferences, trained via EM, but failed to achieve competitive performance on a pseudodisambiguation task.
The models described above have subsequently been used in many different studies. For example: McCarthy and Carroll (2003) use Li and Abe's method in a word sense disambiguation setting; Schulte im Walde et al. (2008) use their MDL approach as part of a system for syntactic and semantic subcategorisation frame learning; Shutova (2010) deploys Resnik's method for metaphor interpretation. Brockmann and Lapata (2003) report a comparative evaluation in which the methods of Resnik and Clark and Weir outpeform Li and Abe's method on a plausibility estimation task.
Much recent work on preference learning has focused on purely distributional methods that do not use a predefined hierarchy but learn to make generalisations about predicates and arguments from corpus observations alone. These methods can be vectorbased (Erk et al., 2010;Thater et al., 2010), discriminative (Bergsma et al., 2008) or probabilistic (Ó Séaghdha, 2010;Ritter et al., 2010;Reisinger and Mooney, 2011). In the probabilistic category, Bayesian models based on the "topic modelling" framework (Blei et al., 2003b) have been shown to achieve state-of-the-art performance in a number of evaluation settings; the models considered in this paper are also related to this framework.
In machine learning, researchers have proposed a variety of topic modelling methods where the latent variables are arranged in a hierarchical structure (Blei et al., 2003a;Mimno et al., 2007). In contrast to the present work, these models use a relatively shallow hierarchy (e.g., 3 levels) and any hierarchy node can in principle emit any vocabulary item; they thus provide a poor match for our goal of modelling over WordNet. Boyd-Graber et al. (2007) describe a topic model that is directly influenced by Abney and Light's Markov model approach; this model (LDAWN) is described further in Section 3.3 below. Reisinger and Paşca (2009) investigate Bayesian methods for attaching attributes harvested from the Web at an appropriate level in the WordNet hierarchy; this task is related in spirit to the preference learning task.
3 Probabilistic modelling over WordNet

Notation
We assume that we have a lexical hierarchy in the form of a directed acyclic graph G = (S, E) where each node (or synset) s ∈ S is associated with a set of words W n belonging to a large vocabulary V . Each edge e ∈ E leads from a node n to its children (or hyponyms) Ch n . As G is a DAG, a node may have more than one parent but there are no cycles. The ultimate goal is to learn a distribution over the argument vocabulary V for each predicate p in a set P , through observing predicate-argument pairs. A predicate is understood to correspond to a pairing of a lexical item v and a relation type r, for example p = (eat, direct object). The list of observations for a predicate p is denoted by Observations(p).

Cut-based models
The first model we consider, WN-CUT, is directly inspired by Li and Abe's model (2). Each predicate p is associated with a distribution over "cuts", i.e., complete subgraphs of G rooted at a single node and containing all nodes dominated by the root. It follows that the number of possible cuts is the same as the number of synsets. Each cut c is associated with a non-uniform distribution over the set of words W c that can be generated by the synsets contained in c. As well as the use of a non-uniform emission distribution and the placing of Dirichlet priors on the multinomial over cuts, a significant difference from Li and Abe's model is that overlapping cuts are permitted (indeed, every cut has non-zero probability given a predicate). For example, the model may learn that the direct object slot of eat gives high probability to the cut rooted at food#n#1 but also that the cut rooted at substance#n#1 has non-negligible probability, higher than that assigned to phenomenon#n#1. It follows that the estimated probability of p taking argument w takes into account all possible cuts, weighted by their probability given p.
The generative story for WN-CUT is given in Algorithm 1; this describes the assumptions made by the model about how a corpus of observations is generated. The probability of predicate p taking argument w is defined as (4); an empirical posterior estimate of this quantity can be computed from a Gibbs sampling state via (5): where f cw is the number of observations containing argument w that have been assigned cut c, f cp is the number of observations containing predicate p that have been assigned cut c and f c· , f ·p are the marginal counts for cut c and predicate p, respectively. The two terms that are multiplied in (4) play complementary roles analogous to those of the two description lengths in Li and Abe's MDL formulation; P (c|p) will prefer to reuse more general cuts, while P (w|c) will prefer more specific cuts with a smaller associated argument vocabulary. As the number of words |W c | that can be emitted by a cut |c| varies according to the size of the subhierarchy under the cut, the proportion of probability mass accorded to the likelihood and the prior in (5) is not constant. An alternative formulation is to keep the distribution of mass between likelihood and prior constant but vary the value of the individual β c parameters according to cut size. Experiments suggest that this alternative does not differ in performance.
The second cut-based model, WN-CUT-TOPICS, extends WN-CUT by adding two extra layers of latent variables. Firstly, the choice of cut is conditional on a "topic" variable z rather than directly conditioned on the predicate; when the topic vocabulary Z is much smaller than the cut vocabulary C, this has the effect of clustering the cuts. Secondly, instead of immediately drawing a word once a cut has been chosen, the model first draws a synset s and then draws a word from the vocabulary W s associated with that synset. This has two advantages; it directly disambiguates each observation to a specific synset rather than to a region of the hierarchy and it should also improve plausibility predictions for rare synonyms of common arguments. The generative story for WN-CUT-TOPICS is given in Algorithm 2; the distribution over arguments for p is given in (6) and the corresponding posterior estimate in (7): As before, f zp , f cz , f sc and f ws are the respective co-occurrence counts of topics/predicates, cuts/topics, synsets/cuts and words/synsets in the sampling state and f ·p , f ·z , f ·c and f ·s are the corresponding marginal counts.
Since WN-CUT and WN-CUT-TOPICS are constructed from multinomials with Dirichlet priors, it is relatively straightforward to train them by collapsed Gibbs sampling (Griffiths and Steyvers, 2004), an iterative method whereby each latent variable in the model is stochastically updated according to the distribution given by conditioning on the current latent variable assignments of all other tokens. In the case of WN-CUT, this amounts to updating the cut assignment c i for each token in turn. For WN-CUT-TOPICS there are three variables to update; c i and s i must be updated simultaneously, but z i can be updated independently for the benefit of efficiency. Although WordNet contains 82,115 noun synsets, updates for c i and s i can be computed very efficiently, as there are typically few possible synsets for a given word type and few possible cuts for a given synset (the maximum synset depth is 19).
The hyperparameters for the various Dirichlet priors are also reestimated in the course of learning; the values of these hyperparameters control the degree of sparsity preferred by the model. The "top-level" hyperparameters α in WN-CUT and κ in WN-CUT-TOPICS are estimated using a fixed-point iteration proposed by Wallach (2008); the other hyperparameters are learned by slice sampling (Neal, 2003). Abney and Light (1999) proposed an approach to selectional preference learning in which arguments are generated for predicates by following a path λ = (l 1 , . . . , l |λ| ) from the root of the hierarchy to a leaf node and emitting the corresponding word. The path is chosen according to a Markov model with transition probabilities specific to each predicate. In this model, each leaf node is associated with a single word; the synsets associated with that word are the immediate parent nodes of the leaf. Abney and Light found that their model did not match the performance of Resnik's (1993) simpler method. We have had a similar lack of success with a Bayesian version of this model, which we do not describe further here.

Walk-based models
Boyd-Graber et al. (2007) Create a path starting at the root synset λ 0 : while not at a leaf node do λ t+1 ∼ M ultinomial(Ψ z i ,λt ) end while Emit the word at the leaf as w i end for end for corpus is associated with a distribution over topics and each topic is associated with a distribution over paths. The clustering effect of the topic layer allows the documents to "share" information and hence alleviate problems due to sparsity. By analogy to Abney and Light, it is a short and intuitive step to apply LDAWN to selectional preference learning. The generative story for LDAWN is given in Algorithm 3; the probability model for P (w|p) is defined by (8) and the posterior estimate is (9): where 1[λ → w] = 1 when the path λ leads to leaf node w and has value 0 otherwise. Following Boyd-Graber et al. the Dirichlet priors on the transition probabilities are parameterised by the product of a strength parameter σ and a distribution α s , the latter being fixed according to relative corpus frequencies to "guide" the model towards more fruitful paths. Gibbs sampling updates for LDAWN are given in Boyd-Graber et al. (2007). As before, we reestimate

Experimental procedure
We evaluate our methods by comparing their predictions to human judgements of predicate-argument plausibility. This is a standard approach to selectional preference evaluation (Keller and Lapata, 2003;Brockmann and Lapata, 2003;Ó Séaghdha, 2010) and arguably yields a better appraisal of a model's intrinsic semantic quality than other evaluations such as pseudo-disambiguation or held-out likelihood prediction. 2 We use a set of plausibility judgements collected by Keller and Lapata (2003). This dataset comprises 180 predicateargument combinations for each of three syntactic relations: verb-object, noun-noun modification and adjective-noun modification. The data for each relation is divided into a "seen" portion containing 90 combinations that were observed in the British National Corpus and an "unseen" portion containing 90 combinations that do not appear (though the predicates and arguments do appear separately). Plausibility judgements were elicited from a large group of human subjects, then normalised and logtransformed. Table 1 gives a representative illustration of the data. Following the evaluation inÓ Séaghdha (2010), with which we wish to compare, we use Pearson r and Spearman ρ correlation coefficients as performance measures. All models were trained on the 90-million word written component of the British National Corpus, 3 lemmatised, POS-tagged and parsed with the RASP toolkit (Briscoe et al., 2006). We removed predicates occurring with just one argument type and all tokens containing non-alphabetic characters. The resulting datasets consist of 3,587,172 verbobject observations (7,954 predicate types, 80,107 argument types), 3,732,470 noun-noun observations (68,303 predicate types, 105,425 argument types) and 3,843,346 adjective-noun observations (29,975 predicate types, 62,595 argument types).
All the Bayesian models were trained by Gibbs sampling, as outlined above. For each model we run three sampling chains for 1,000 iterations and average the plausibility predictions for each to produce a final prediction P (w|p) for each predicate-argument item. As the evaluation demands an estimate of the joint probability P (w, p) we multiply the predicted P (w|p) by a predicate probability P (p|r) estimated from relative corpus frequencies. In training we use a burn-in period of 200 iterations, after which hyperparameters are reestimated and P (p|r) predictions are sampled every 50 iterations. All probability estimates are log-transformed to match the gold standard judgements.
In order to compare against previously proposed selectional preference approaches based on Word-Net we also reimplemented the methods that performed best in the evaluation of Brockmann and Lapata (2003): Resnik (1993) and Clark and Weir (2002). For Resnik's model we used WordNet 2.1 rather than WordNet 3.0 as the former has multiple roots, a property that turns out to be necessary for good performance. Clark and Weir's method requires that the user specify a significance threshold α to be used in deciding where to cut; to give it the best possible chance we tested with a range of values (0.05, 0.3, 0.6, 0.9) and report results for the best-performing setting, which consistently was α = 0.9. One can also use different statistical hypothesis tests; again we choose the test giving the best results, which was Pearson's chi-squared test. As this method produces a probability estimate conditioned on the predicate p we multiply by a MLE estimate of P (p|r) and log-transform the result. eat food#n#1, aliment#n#1, entity#n#1, solid#n#1, food#n#2 drink fluid#n#1, liquid#n#1, entity#n#1, alcohol#n#1, beverage#n#1 appoint individual#n#1, entity#n#1, chief#n#1, being#n#2, expert#n#1 publish abstract entity#n#1, piece of writing#n#1, communication#n#2, publication#n#1   .620 . 614 .196 .222 .544 .604 .114 .125 .543 .622 .135 .102 LDA .504 .541 .558 .603 .615 .641 .636 .666 .594 .558 .468 .459

Results
Table 2 demonstrates the top cuts learned by the WN-CUT model from the verb-object training data for a selection of verbs. Table 3 gives quantitative results for the WordNet-based models under consideration, as well as results reported byÓ Séaghdha (2010) for a purely distributional LDA model with 100 topics and a Maximum Likelihood Estimate model learned from the BNC. In general, the Bayesian WordNet-based models outperform the models of Resnik and Clark and Weir, and are competitive with the state-of-the-art LDA results. To test the statistical significance of performance differences we use the test proposed by Meng et al. (1992) for comparing correlated correlations, i.e., correlation scores with a shared gold standard. The differences between Bayesian WordNet models are not significant (p > 0.05, two-tailed) for any dataset or evaluation measure. However, all Bayesian models improve significantly over Resnik's and Clark and Weir's models for multiple conditions. Perhaps surprisingly, the relatively simple WN-CUT model scores the greatest number of significant improvements over both Resnik (7 out of 12 conditions) and Clark and Weir (8 out of 12), though the other Bayesian models do follow close behind. This may suggest that the incorporation of WordNet structure into the model in itself provides much of the clustering benefit provided by an additional layer of "topic" latent variables. 4 In order to test the ability of the WordNet-based models to make predictions about arguments that are absent from the training vocabulary, we created an artificial out-of-vocabulary dataset by removing each of the Keller and Lapata argument words from the input corpus and retraining. An LDA selectional preference model will completely fail here, but we hope that the WordNet models can still make relatively accurate predictions by leveraging the additional lexical knowledge provided by the hierarchy. For example, if one knows that a tomatillo is classed as a vegetable in WordNet, one can predict a relatively high probability that it can be eaten, even though the word tomatillo does not appear in the BNC.
As a baseline we use a BNC-trained model that   .231 Table 4: Forced-OOV results (Pearson r and Spearman ρ correlations) on Keller and Lapata's (2003) plausibility data predicts P (w, p) proportional to the MLE predicate probability P (p); a distributional LDA model will make essentially the same prediction. Clark and Weir's method does not have full coverage; if no sense s of an argument appears in the data then P (s|p) is zero for all senses and the resulting prediction is zero, which cannot be log-transformed.
To sidestep this issue, unseen senses are assigned a pseudofrequency of 0.1. Results for this "forced-OOV" task are presented in Table 4. WN-CUT proves the most adept at generalising to unseen arguments, attaining the best performance on 7 of 12 dataset/evaluation conditions and a statistically significant improvement over the baseline on 6. We observe that estimating the plausibility of unseen arguments for noun-noun modifiers is particularly difficult. One obvious explanation is that the training data for this relation has fewer tokens per predicate, making it more difficult to learn their preferences. A second, more hypothetical, explanation is that the ontological structure of WordNet is a relatively poor fit for the preferences of nominal modifiers; it is well-known that almost any pair of nouns can combine to produce a minimally plausible nounnoun compound (Downing, 1977) and it may be that this behaviour is ill-suited by the assumption that preferences are sparse distributions over regions of WordNet.

Conclusion
In this paper we have presented a range of Bayesian selectional preference models that incorporate knowledge about the structure of a lexical hi-erarchy. One motivation for this work was to test the hypothesis that such knowledge can be helpful in constructing robust models that can handle rare and unseen arguments. To this end we have reported a plausibility-based evaluation in which our models outperform previously proposed WordNetbased preference models and make sensible predictions for out-of-vocabulary items. A second motivation, which we intend to explore in future work, is to apply our models in the context of a word sense disambiguation task. Previous studies have demonstrated the effectiveness of distributional Bayesian selectional preference models for predicting lexical substitutes (Ó Séaghdha and Korhonen, 2011) but these models lack a principled way to map a word onto its most likely WordNet sense. The methods presented in this paper offer a promising solution to this issue. Another potential research direction is integration of semantic relation extraction algorithms with WordNet or other lexical resources, along the lines of Pennacchiotti and Pantel (2006) and Van Durme et al. (2009).


Using ontology for resume annotation

Employers collect a large number of resumes from job portals, or from the company's own website. These documents are used for an automated selection of candidates satisfying the requirements and therefore reducing recruitment costs. Various approaches for process documents have already been developed for recruitment. In this paper we present an approach based on semantic annotation of resumes for e-recruitment process. The most important task consists on modelling the semantic content of these documents using ontology. The ontology is built taking into account the most significant components of resumes inspired from the structure of EUROPASS CV. This ontology is thereafter used to annotate automatically the resumes.

Introduction
Employers often receive a large number of Resumes for an open position. The costs of classically and manually selecting on appropriate candidates have amplified and employers are searching for tools to automate the candidate's selection. Online recruitment processes can be efficient using Semantic Web technologies (Bizer et al., 2005). Indeed, using Semantic Web Technologies in the recruitment domain could considerably decrease the costs for employers: publishing job offers, and selecting candidates (Morin and Trichet, 2004).
In this paper we investigate how Semantic and Web technologies can be used to support the recruitment process. In particular, we describe the design and implementation of an ontology which defines the semantic content of resumes. We propose in addition an annotation approach of resumes based on this ontology. We also present the results of initial experiments testing the performance of this prototype implementation.
The rest of the paper is organized as follows: Section 2 gives a brief overview of related works of the e-recruitment field. We describe our approach for the ontology creation and the global architecture of the annotation system in section 3. In section 4 an evaluation of our approach is shown, and then a conclusion and perspectives for improving this work are given at the end of this paper.

Related Works
In the field of e-recruitment, the information contained in the resume of a candidate who applies for a job, is specific, and requires semantic and automatic processing. In this context, several approaches conducted under the recruitment (e-recruitment), take into account the semantics of used documents (e.g. resume). Some of them index resumes using semantic techniques that consist mainly on the association of most important elements in a document to concepts existing in the resume. This approach is based mainly on the techniques of Natural Language Processing (NLP).
Other works focus on the semantic annotation approach to enrich documents with their semantic content. This approach seems particularly interesting for its efficiency, and availability of tools and web semantic standards.

Approach of annotation resumes using Gate
In order to facilitate the process of e-recruitment, Amdouni and Ben Abdessalem (Amdouni and Ben Abdessalem Karaa 2010), developed a prototype allowing an automatic annotation of the resume. A non structured resume existing in different formats (Doc, Pdf, HTML, etc) can be transformed into an XML document, structured according to the EUROPASS CV constituents. After that, the structured resume is analyzed to extract the pertinent information as the diploma, experience, name, sex, date of birth, nationality, etc. Therefore, they use the API Gate [http://gate.ac.uk/], extended by new JAPE rules permitting the extraction of the necessary information to structure them according to the EUROPASS CV.
The core component of the prototype is the recognition of the basic elements in the resume. For this purpose, they use Gate components: Sentence Splitter, Tokenizer, Gazetteer, and Named Entity Transducer. First, sentence Splitter component identifies sentences in the resume. A Tokenizer splits each sentence into words (punctuation, numbers …). Gazetteer component creates annotations about entities such as persons, organizations, job titles. Named Entity Transducer is used in the Semantic annotation Step. It applies JAPE rules to the previous annotations to generate additional and specific annotations. However, JAPE rules were extended to extract all the key information from resume. Finally an XML document is generated related to HR-XML EUROPASS CV schema.

Approach of annotation resumes using ontology
Ontology is gaining position in computer science. It facilitates the understanding between persons and organizations. Ontology is a model, or a theory of a particular domain representing a real-world. Recently, the research on ontologies proves it to be an important field in the Information Systems area (Al-Debei, and Fitzgerald, 2009).
The appliance of ontologies in recruitment domain is relevant, since ontology for recruitment can define concepts such as "competency", "skill", attributes of such concepts, and the relationships between these concepts. In consequence, we can define which competencies and skills are required for a certain job and which experience and knowledge is required to attain a certain level of competence.
Competency is the concept that describes the skills and knowledge that individuals should have to be fit for particular jobs (De Leenheer et al., 2010).
A model which could identify competency is highly needed. A competency model is a set of competency elements in relation and characterising the job performance (Chung and Wu, 2011). A competency modelling is taking considerable interest in different area such as recruitment (Mochol et al., 2006), engineering knowledge (Sicilia et al., 2009), learning (Monceaux et al., 2008), and education (Sgouropoulou, 2010).
The ontology based competency modelling approach (Sicilia, 2005), (Draganidis at al., 2006), describes the desirable competence profile of an employer for a given post. It gives a good definition of the relations between competencies. It can be in addition used for competence assessment process.
Several schemas were defined to describe the competences. HRXML specifies the competency format through XML code (http://www.hr-xml.org/). HRXML enclosing human-resource management data specifications, it has an important use for human resource applications.
The IMS consortium (http://www.imsglobal.org) as well as HRXML offers specifications for competencies named "Reusable Definition of Competency or Educational Objective (RDCEO)".
Ontology offers additional modelling elements, through logical descriptions, for defining in competency schemas different types of competency, different relations, and various measurement scales.
Ontology description languages can be useful for representing both the concepts and the Instances of the concepts.
In the context of recruitment applications, ontologies can be directly used to make applications more aware of the domain semantics, such us matching of an individual's competency profile with a requirements profile, e.g. for applicant selection (Mochol et al., 2006).

HR ontology
Bizer et al. (Bizer et al. 2005) have created human resource ontology (HR ontology) composed of subontologies which are used in both job posting and job application descriptions. The HR ontology is derived from existing specifications and standards such as HR-XML standard, HR-BA-XML (German version of HR-XML).

COmmOnCV project
Harzallah et al. (Harzallah et al, 2002), worked on the project CommOnCv 1 . This project offers the opportunity for a job seeker or a recruiter to identify and represent the underlying skills in resume or job offer in a formal way. This formal representation in the form of annotations is used as a reference to refine the process of matching between the resume and the adverts from the job market on the web.
The objective of CommOnCV consists on the definition of a model of competency and a skill management process underlying in a resume or a job offer. The competency model focuses on the recognition of skills including social, organizational, technical, and economic aspects. The competencies are characterized by a set of resume's annotations. These latter, are formally denoted by using semantic web languages such as RDF/RDFs or DAML+OIL. These annotations, which follow a model of competency, are described in relation to domain ontologies. These ontologies can be associated to a particular sector: Finance, Healthcare and/or to a specific company.

OS-SKILL project
According to Rieu et al (Rieu et al., 2005), OS-SKILL project is a method for managing jobs and skills; it is an Internet / Intranet application that can manage a successful business operator in the repositories of trades and skills. It is fully configurable and allows mapping the trades, skills, organizational structure, career management, the tasks of the organization, etc.
OS-SKILL is also a method and a tool: a method of construction trades and skill benchmarks, and a tool for management of jobs and skills.
It provides relevant and effective functionalities independent of management skills, such as staff evaluation, job identification, identification of individuals who need training, analysis situation of the organization, and search for collaborators.
OS-SKILL is based on XML technologies and Web services; it uses the Osia method based on ISO 704, which builds ontology step by step.

ER-ontology
In the context of semantic web, Yahiaoui (Yahiaoui et al., 2006) have proposed an approach of semantic annotation of resumes and job offers in order to automate the process of e-recruitment. This is a simple, detailed, and sufficient solution that determines the necessary elements to the process of annotation.
The objective of this work is to offer coherent and clear documents (resume and job offer) codified in XML, the standard for exchanging data on the web.
Ontology is constructed and implemented in the field of computing and telecommunications to model the semantic content of documents and skills underlying documents. The system proposed in this work focuses on an ontology of Human Resource Management (HRM). It contains several sub-ontologies inter-related and generates annotations from their instantiation. It also operates an XML / HTML server to allow storage and management of resumes and job offers. The software interface allows the automatic annotation of documents. It offers the possibility to job seekers to find the offer that fits with their skills.
The user interface for matching allows interpreting the user queries and the calculation of the degree of semantic matching between user documents and annotated documents.
Job portals Mochol et al. (Mochol et al., 2007) construct a prototype job portal using semantically annotated job offers and applicants. They outline how the technique of query approximation can be the basis for a solution of problems in job search.

Objective work
In the context of e-recruitment problematic and in view of the fact that ontology is an important component of several applications, we propose an approach for resume annotation founded on resume ontology.
The idea is to build and implement an ontology that regroups basic information in the resume. This ontology will be used, after that, in a semantic annotation process of resumes. The ontology to construct has to follow a specific grammar: HR-XML Schema related to EUROPASS CV.
The semantic annotation is a specific metadata (Sicilia, 2006) generation about resumes, aiming to add them formal descriptions (We can identify attributes describing competencies, occupations, etc.). The semantic annotation of resumes can be useful for many human resource applications: retrieval, classification, extraction of element dependencies, analysis of relationships between elements, etc.

The approach
This section describes the resume ontology construction steps in Section A. The ontology is baptized ERECO (E-RECruitment Ontoloy). In the Section B is described the automatic resume annotation system, called E-RecSys (E-Recruitment System), using ERECO ontology.

A. Construction of the resume ontology ERECO
To construct our ontology, we make use of two international standards: HR-XML and EUROPASSCV.

EUROPASS CV
The EUROPASS Curriculum Vitae (EUROPASS CV) 2 enables users to document the development of their qualification profile in a standardised format systematically and chronologically. It encloses personal information in addition to details of any education and training, work experience, skills and competences that the individual has. It aims to offer to users a standardized document at European level. It can be filled in online, in all European languages, and in different formats ((PDF, XML, HTML, …). The EUROPASS CV can be considered as an important tool for better transparency of qualifications and competences both for applicants and potential employers at home and abroad. It contains information about individual: • Personal information: contains eight fields: first name(s)/surname(s), address (es), telephone(s), faxe(s), email, nationality, date of birth and gender. • Work experience: concerns the occupation or position held, date, and main activities and responsibilities.
• Education and training: describes study contents, date, skills covered, and level in national or international classification.
• Personal skills and competences: this part is dedicated to skills and competences acquired in the individual life. It concerns languages, technical skills and competences, social, organisational, technical skills and competences, computer skills and competences, artistic skills and competences, driving licence, and other skills and competences • Additional information: comprises any other information that may be relevant, for example contact persons, references, etc.

Is-a Is-a
Is-a information related to human resources management. The published specifications are free for access.
The standardization of resume is supported by HR-XML. Indeed with HR-XML, a resume may contain the competencies of the applicant in a standardized manner.
In this work, we created a HR-XML schema for resume regarding the EUROPASS CV. Hence, the different items of EUROPASS CV (work experience, education and training, personal skills and competences, etc.) will be described by standard specifications in HR-XML.
Our ontology required to respect the HR-XML schema related to EUROPASSCV.

The ontology ERECO
A multitude of ontological engineering methods exists, describing the stages to follow for the construction of ontology. The design of our ontology is guided by the method developed by the University of STANFORD (Noy and Mcguinness, 2002). It includes the following seven steps: • Determine the domain and scope of the ontolog.

• Identify the important terms of the ontolog.y • Define the classes and the hierarchy of classes. • Define the properties of the classes (the attributes).
• Define the facets of the attributes.
• Create instances of the classes.
Step 1: Determine the domain and scope of the ontology In this step, we start by answering a set of basic questions that helps to determine the domain and the range of the ontology: Question: what is the domain that the ontology is going to cover?
Answer: HRM, e-recruitment, International standards (HR-XML and EUROPASS CV) are also a part of the context.
Question: for what we are going to use the ontology? Answer: for resume annotation Question: what kinds of questions will the ontology give answers?
Answer: what degree? , What experience, what competence, etc.
Question: who is going to use and to assure the maintenance of the ontology?
Step 2: Consider reusing existing ontologies We will assume that no appropriate ontologies subsist and begin developing the ontology from scratch.
Step 3: Identify the important terms of the ontology During this stage, it is important to identify the domain knowledge by establishing a complete list of the terms in the corresponding domain of interest in non structured form. It is necessary to know the concepts, the relations, the rules and the constraints. For the resume ontology, we define for example: Profile, age, telephone, professional experience, sex, nationality, education, formation, establishment, language, diploma, university, certificate, level, software, mention, expertise, etc. This step is guided by information contained in the EUROPASS CV. Step

4: Define the classes and the hierarchy of classes
In the previous stage, we identified, for the ontology, a list of non structured terms, now, it is necessary to define classes by selecting the terms that describe the objects having an independent existence. It is necessary to organize these classes in a hierarchical taxonomy.
Step 5: Define the properties of the classes (the attributes) At this stage, it is coherent to assign some properties for the definite classes. The properties will be attached to the classes. If an attribute is connected to the most general class, then all under classes inherit this attribute. Also, it is recommended to affect some values by default to the class attributes.
Step 6: Define the facets of the attributes In this step, we define the value type of the attributes: the types of value capable to be affected to an attribute such as: number, string, character, Boolean… Also, we designate the number of values (cardinality) that an attribute can have, this cardinality can be unique or multiple. We identify the domain, the rank of an attribute and the relations between classes. The following figure (Fig. 1.) is an UML class diagram showing the design of ERECO ontology.
Step 7: Create instances of the classes This stage consists on creating the instances of the classes that represent real entities.
The ontology population guarantees the efficiency of the annotation. We used the lexicographic data base WordNet for the instantiation of some classes of the ontology in a semiautomatic way.
WordNet is a lexical network developed by the Cognitive Science Laboratory (Princeton University) under the direction of George A. Miller and Christiane Fellbaum [http://www.cogsci.princeton.edu/~wn / \2010]; it covers the names, the verbs, the adjectives and the adverbs. About 150 000 words are organized in wholes of synonyms named synsets permitting to regroup the terms denoting a given concept. In this work we collected for example from WordNet, all the appropriate ontology instances of the concepts "language", "diploma", "nationality", etc. The instances of the other concepts are introduced manually.

B. Annotation system E-RecSys
The ontology ERECO is afterwards exploited in the annotation process of resumes. We proposed a system that we called E-RecSys ensuring the annotation of resumes using ERECO ontology. The overall system architecture is shown in Figure (Fig. 3.), it consists of five phases:

Phase 1
The first phase involves the selection of resumes in a corpus in different formats (doc, XML, PDF, HTML). Phase 2 The second phase is the treatment of resume; it begins by cutting the resume into words, and then analyses each word by identifying its category. In this phase we used a morphological dictionary containing 290,460 entries, which are associated with a morphological code as the coding dictionary DELAS (Courtois and Silberztein, 1990). The morphological dictionary is composed of simple words with no separator, in small letters under their canonical form, indicating the part of speech: verbs (V), names (N), adjectives (A), adverbs (ADV). Phase 3 The third phase refines the list of words, by keeping only the interesting ones (nouns, adjectives, adverbs ...) and omit others like prepositions, and articles. Phase 4 Once the words are refined, in this phase we take advantage of ERECO, which gathers all the concepts that may exist in a resume (experience, competency, training, etc.) and their properties (name, degree, doùain, etc.) and relations, to annotate automatically the resumes. Phase 5 Once the resumes are annotated, we can in this last phase classify them according to different criteria according to the employer's requirements. This classification will be used in finding simply the most suitable candidate.
We opted for java (Jbuilder) as a programming language for the implementation of E-RecSys annotation system. An API (Application Programmation Interface) JAVA allows the access to the ontology within the editor Protégé-2000 (Fig 4).
The result of annotation with E-Rec-Sys can be displayed in an HRXML format (Fig 5).

Evaluation
To evaluate an annotation system, we have to compare the result of the system with the annotation made manually (by an expert) For the evaluation of E-Rec-Sys, we have annotated the corpus of resumes semi-automatically using the software Gate [http://gate.ac.uk/ ], (Maynard et al., 2000); it is an environment that offers a user the possibility to annotate a document using the plugin Gate Ontology Annotation Tool (OAT). This API allowed us to annotate document (resume) using the ontology ERECO imported with Gate. The concepts of the ontology are displayed, and the expert can associate for each term in the resume the appropriate concept of the ontology (Fig.6).  The two annotated documents (the resume annotated with our annotation system E-Rec-Sys and the resume annotated semi-automatically) are used as inputs for the computation of the statistical metrics: Precision, Recall, and F-measure. These parameters are widely used for evaluating such systems. A high recall indicates that you haven't missed anything; a high precision reveals that all returned results were relevant, and F-measure combines exactness (precision) and completeness (recall).
Recall is computed as the fraction of correct annotated words among all truly annotated words: We used the annotation tool AnnotationDiff (Maynard, et al., 2001), which is a Gate plug-in that allows automatic evaluation systems. Indeed, it can compare two sets of annotation; a document annotated automatically with another annotated manually.
The figure (Fig. 7.) shows the result of the evaluation using the document annotated semi-automatically with Gate (CVgate) and the document annotated by E-Rec-Sys (CVxml).
This result shows that we have six partially correct annotations. The performance metrics Recall, Precision and F-measure are (0, 0, 0) when we consider that the partially correct annotations are false. However, when we consider that the partially correct annotations are correct annotations, the performance metrics Recall, Precision and F-measure turn into (1, 1, 1).
Using the same approach, we complete our evaluation using a corpus gathering 300 resumes downloaded from the site (www.emploi.nat.tn ) and from the site (http://www.e-marketing.fr/Emploi/Recherche/CV-Flash.asp).
The tables below show the performance metrics for personal information (Table I), and other resume information (Table II): As shown in tables (Table I) and (Table II), the results are Satisfactory since the values are close to 1. Indeed, the Precision varies between 0.78 and 1; Recall varies from 0.8 to 0.97, and the F-measure between 0.79 and 0.99.
We compared our results with the results of (Amdouni and Ben Abdessalem, 2010) (Table III) and (Table IV). We noted that both works are very close in terms of performance; the difference between metric values is minor.  However, according to Table (Table III), the F-measure of E-Rec-Sys is better then Amdouni and Ben Abdessalem work in annotating the concepts of : Name, Gender, nationality, date, tel, establishment and language. Nevertheless, Amdouni and Ben Abdessalem work is better in annotating: Email, competence, and training with values very close to ours.
We wanted to test whether corpus size influences the response time of annotation. We measured the response time of our system during the annotation process of resumes for 1, 10, 50, 100, 150, …, and total 300 resumes.
The result is presented in the table above (TableV).
These results show that the response time during the annotation process is not strongly influenced by the corpus size, for 10 resume, for example, the response time is 1mn 15s, which is lower than 10 resume* 10s.

Conclusion
Employers often collect a huge quantity of resumes for an open post. In order to decrease management costs employers have begun to choose online resumes rather then classic ones. The resumes are used for the automated selection of candidates satisfying the requirements. For this purpose annotations are useful for facilitating the selection process by matching the requirements with the resumes. We claim that using Semantic Web technologies (ontology) is helpful for the resume annotations.
In this paper we presented a scenario for supporting recruitment processes. We suggested an annotation approach of resumes based on ontology and we described our prototypical implementation.
We will focus our future work on the refinement of the prototype, and integrating a component for the semantic matching between demand (resume) and supply (requirement).


extfieldsofstudy:
Computer Science
Physics

text:
iAQC: The Intensity-Aware Quantum Cryptography Protocol

This paper reports a variant of the three-stage quantum cryptography protocol which can be used in low intensity laser output regimes. The variant, which tracks the intensity of the laser beam at the intermediate stages, makes the task of the eavesdropper harder than the standard K06 protocol. The constraints on the iAQC protocol are much less than those on BB84 and in principle it can not only be used for key distribution but also for direct bitwise encryption of data. The iAQC protocol is an improvement on the K06 protocol in that it makes it harder for the eavesdropper to monitor the channel.

Introduction
We present here a variant of the three-stage quantum cryptography protocol [1], sometimes called the K06 protocol, which has protection against eavesdropping built into it. The 3-stage quantum cryptography protocol is based on random rotations (or other commutative operators) which can better protect duplicate copies of the photons than in non-single qubit transmissions of BB84. This protocol can use attenuated pulse lasers rather than single-photon sources in the quantum key exchange, which makes it possible to transmit the pulses over a greater distance.
The theoretical basis of the K06 protocol is the fact that unknown pure states carry information [2], [3], [4] even though the von Neumann entropy of such states equals zero.
In this new protocol, which we call iAQC protocol, both Alice and Bob monitor the intensity of the light beam coming to them in the intermediate stages of the protocol. Doing so makes it possible for Alice and Bob to determine if any photons have been siphoned off by the eavesdropper. This tracking can be done by measuring a pre-set fraction of the incoming beam.
This makes the task of Eve, the eavesdropper, harder than it would be without the intensity awareness feature. If intensity is not tracked then iAQC is identical to K06. The use of random transformations, which Alice and Bob can change from one qubit to another, guarantees that from the perspective of the eavesdropper, the probability of collapsing into 〉 0 and 〉 1 states has equal probability, which is desirable for cryptographic security.
As we can see, while the actual quantum state of X is never exposed on the link, Bob is able to restore X.
for implementing U A (X) and U B (X) as R(θ) and R(φ).
Unlike the BB84 protocol which is vulnerable to siphoning of photons in an attenuated pulsed laser system, the 3-stage protocol is immune to such an attack since the actual quantum state of the key is never revealed in the communication. This property is of significant importance in terms of using quantum cryptography in a practical network environment where an optical path can potentially be extended beyond trusted routers.
In iAQC, the intensity-aware protocol, the intensity of the beam generated by Alice is publicly announced [5]. For the sake of simplicity of presentation it will be assumed that there is no loss in intensity during transmission from Alice to Bob. In practice, this loss can be factored in the protocol. The protocol is as follows: Step 1. Alice uses photons of intensity I (which is publicly known) to Bob and performs a polarization rotation of angle θ.
Step 2. Bob uses a partially silvered mirror (or some suitable beam-splitter) to divert fraction k of the incoming beam to measure its intensity. He applies another random rotation φ on the remaining beam of intensity I(1-k) and transmits it to Alice.
Step 3. Alice receives the beam of intensity I(1-k) and diverts a fraction k of it to measure its expected intensity and undoes her random rotation of angle θ and retransmits the beam of intensity I(1-k) 2 to Bob.
Step 4. Bob uses the intensity-testing portion of it I(1-k) 2 k for checking it and uses the rest of the beam of intensity I(1-k) 3 to determine the value of the qubit. The eavesdropper will be detected by Alice and Bob if the intensity of the beam reaching them in the three stages is less than expected.
The constraint on the maximum number of photons being used in the transmissions between Alice and Bob is much less severe than in BB84. If a single photon is transmitted then the system is provably secure. Let us assume that Alice and Bob each uses s different rotation angles. Eve needs to have access to each of the three transmissions to be able to break the system. Assuming that she needs m photons to determine which one of the s rotation angles were used by Alice and Bob, the total number she needs to siphon off is 3m. If the photon source produces 6m photons, the siphoning off of 3m photons would reduce the intensity by a factor of 2. The intensity used could be a clearly defined variable of the system and any reduction in it would be obvious to Bob and therefore the eavesdropper would be found out.
Also note that m >> s, therefore, the laser source output can consist of many photons. From information theoretic point of view, the number of photons required to distinguish between s rotation angles is log 2 s. Therefore, the minimum number of photons that need to be siphoned off by the eavesdropper is 3log 2 s. In reality, the number of photons to be siphoned off will be significantly greater.
If the technique of using s photons each fed into detectors aligned to different polarizations is used then one requires a total of 3s photons to be siphoned off by Eve to determine the three different polarization angles. If the detectors used by Bob and Alice to check the intensities at intermediate stages can determine reduction of intensity by a factor of one-half, then the source can use 6s photons in each burst. In reality the constraints are even less severe as the bases used by Alice and Bob are arbitrary as long as they are in the same plane.

Siphoning Attack on K06 and iAQC
Eve can fool Alice and Bob into believing that no photons have been siphoned off if she injects the number of random photons equal to the ones she has taken from the beam. But this can only be done at a cost to her ability to tap the exchange. If she withdraws g percent of the photons and injects the same number of some known polarization, the probability that she will be able to 6 determine the polarization angles of the siphoned photons will go down in the next two passes.
Furthermore, Bob would know that siphoning had taken place from the fact that the measured photons will not all have the same polarization.
To see this, assume that Alice sends 6 photons and Eve takes out 1 photon in each link. The following example picture describes the situation: Table 1. The workings of the iAQC protocol Bob would be easily able to determine that Eve had siphoned off the photons since all his photons will not be aligned.

Conclusions
The BB84 protocol for quantum key distribution (QKD) and its variants [6], [7] deal with the secure exchange of key between sender and utilizing the quantum properties of photons. The major threat to the security of QKD algorithms comes from the fact that the constraints on the implementation of the optical apparatus used in these protocols are extreme. BB84 is provable secure only if the photon sources produces single photons [8] and the detector can detect single photons. Recently, industry implementations of the protocol that were thought to be secure were successfully hacked [9], [10]. Although patches for these attacks have been introduced, there is no evidence at this point that other loopholes in the implementation do not accept. On the other hand, if the average photon rate is much less than one as used in the implementation schemes of idQuantique and MagiQ, the overall rate of a few thousand bits per second makes the system unsuitable for quantum cryptography of continuous data and that is the reason why it is used only for quantum key distribution. Current systems employ symmetric classical cryptography after the key has been exchanged using BB84.

Alice Sends
The constraints on the iAQC protocol are much less than those on BB84. The iAQC protocol is an improvement on the K06 protocol in that it makes it harder for the eavesdropper to monitor the channel. An analysis of the performance of the iAQC protocol in the presence of noise remains to be done. For this analysis further information on the number of photons used and capability to determine polarization states will be required [11].


extfieldsofstudy: Mathematics Medicine Physics

text:
Determining the Solution Space of Vertex-Cover by Interactions and Backbones

To solve the combinatorial optimization problems especially the minimal Vertex-cover problem with high efficiency, is a significant task in theoretical computer science and many other subjects. Aiming at detecting the solution space of Vertex-cover, a new structure named interaction between nodes is defined and discovered for random graph, which results in the emergence of the frustration and long-range correlation phenomenon. Based on the backbones and interactions with a node adding process, we propose an Interaction and Backbone Evolution Algorithm to achieve the reduced solution graph, which has a direct correspondence to the solution space of Vertex-cover. By this algorithm, the whole solution space can be obtained strictly when there is no leaf-removal core on the graph and the odd cycles of unfrozen nodes bring great obstacles to its efficiency. Besides, this algorithm possesses favorable exactness and has good performance on random instances even with high average degrees. The interaction with the algorithm provides a new viewpoint to solve Vertex-cover, which will have a wide range of applications to different types of graphs, better usage of which can lower the computational complexity for solving Vertex-cover.

INTRODUCTION
The minimal vertex-cover problem (Vertex-cover) belongs to one of Karp's 21 NPcomplete problems [1] and the six basic NP-complete problems [2,3], which is considered as one of the classical problems in theoretical computer science. The aim of this problem is to mark a minimum subset of vertices such that there are at least one vertex of each edge in the subset. There are a large number of applications of this problem in the related real networks, such as immunization strategies in networks [4] and monitoring of internet traffic [5].
There is a threshold behavior of the minimum vertex-cover problem on the Erdös-Rényi random graph [6]. It means that the typical running time of algorithms changes to exponential from polynomial when the order parameter becomes lager than the Euler number e [7,8]. This phase transition phenomenon is considered to have intrinsic correspondence with the clustering structure of solution space which have already been observed in statistical physics when studying spin glasses [9,10]. Although most statistical physicists believe that the clustering structure leads to the failure of replica symmetry, the details of the relation between searching solutions and the structure are not well established, and how the clustering structure looks like is far from being clear for most models [11][12][13]. From an algorithmic point of view, the solutions' structure makes great effects on the algorithm to find the solutions, which sets barriers to local searching algorithms and makes the computation expensive [14,15]. So the features of solutions' structure are explored by different approaches. Till now, some typical structures such as clustering, backbone, backdoor [16] and frustration [17], have been widely investigated to understand the structure of solutions more clearly. Especially, H. Zhou [17,18] has proposed the long-range frustration structure and F. Krzakala [19] has provided a formal definition as long-range correlation. The longrange correlation and bakbone structures are treated as the origin of the replica symmetric breaking and the high computational complexity. And, based on the analysis of these typical characteristics of the solution space, many efficient searching algorithms are proposed to solve NP-complete problems, such as Belief Propagation and Survey Propagation [20][21][22].
In this paper, a mutual-determination structure is proposed by statistical mechanic approach to investigate the solution space of the minimum vertex-cover problem. This structure reflects the feature of the Hamming distance [23,24] among solutions and describes how tight the correlations among unfrozen variables are. By this structure, we can detect the equivalent variables in the solution space [25], i.e., the variables must take the same or the opposite Boolean values. Furthermore, based on the existence of the mutual-determination in the solution space of Vertex-cover, the ranks of nodes of a graph by the leaf-removal process are provided to describe the influence orders of leaves in different levels. Taking the advantage of the leaf-removal ranks and the relationship of mutual-determination with the backbone and unfrozen variables, we can have a much clear understanding of the evolution of the states in the solution space when a new node is added, and a reduced solution graph is defined to exactly express the structural information of the solution (sub-)space. Finally, an algorithm named Mutual-determination and Backbone Evolution Algorithm is proposed by the evolution of the mutual-determinations and backbones on the reduced solution graph, and some analysis and numerical experiments are given to verify its efficiency and adaptability. This algorithm is complete to find the whole solution space of Vertex-cover when there is no leaf-removal core in the graph, otherwise an approximated one with relatively better efficiency than the replica symmetry methods.

DEFINITION OF INTERACTION
A vertex cover on an undirected graph G(N, M) with N nodes and M edges is a subset S = {i 1 , i 2 , · · · , i m } of its nodes such that every edge has at least one endpoint in S. The minimum vertex-cover problem is an optimization problem to find the minimum size of a vertex cover on a given graph. Mapped to spin-glass model, energy function of the minimum vertex-cover problem can be written as where E(G) denotes the edge set and (i, j)s are edges in it, spin/variable σ i = −1 if node i ∈ S (covered) and σ i = 1 otherwise. Then, different energy levels are produced by different assignments or configurations in terminology of spin-glass theory. The assignments with the lowest energy are named solutions/ground states, and the set of all these solutions achieving the lowest energy (minimum vertex cover) is named solution space S.
Backbones [16] and long-range correlations [17,19] are both the typical structures of solution space of combinatorial optimization problems, which have been well studied in 3 algorithmic and statistical analysis. In the solution space S, spin σ i is frozen or called backbone if it takes the same value in all solutions; otherwise it is unfrozen. For an unfrozen spin σ i , if it taking some value will make influence on infinite number of other spins (assumed O(N) with the total number of N spins), it belongs to long-range correlation [18,19].
Recent research suggests that the complicated organizations of the solutions of combinatorial optimizations, e.g., backbones and long-range correlations, would be the kernel reason for the algorithmic hardness to find a solution for large-scale combinatorial optimization problems with massive constraints and variables [26]. To study the solution space S of Vertex-cover, we classify the variables as unfrozen, positively frozen (frozen to +1) and negatively frozen (frozen to −1) variables.
As a generalization of the backbone and long-range correlation, a new structure named mutual-determination is proposed to achieve a better understanding of the solution space, which can be viewed as an interactive relation of unfrozen variables in the solution space. If two unfrozen variables form a mutual-determination, the fixation of the assignment of any one will result in the fixation of the other in the solution space. Indeed, it is a special relation implied by the constraints that two unfrozen variables can be mutually determined by each other, i.e., if two unfrozen variables σ i , σ j form a mutual-determination, then σ i + σ j = 0.
When two unfrozen nodes form mutual-determination for Vertex-cover, it means that if one of them is covered, the other should be uncovered, and there is one and only one should be covered for this pair of nodes.
By the famous survey propagation algorithm [21], it takes advantage of the idea of the backbone and long-range correlation to gradually eliminate variables and constraints of the original problem in size, and achieves excellent performance for solving 3-SAT, Vertexcover, etc. As the motivation for proposing the mutual-determination structure and for that the variables in interactive relations are equivalent variables, we can use a simple logic σ j = −σ i to decrease the number of variables in the original problem to obtain new algorithmic strategies. In the following sections, we will use the backbones and mutualdeterminations to analyze the solution space of Vertex-cover. There are three leaves in the graph which are marked by the red rectangles in subgraph (2)(3)(4), and the relations among the nodes are revealed by the constraints in the leaves for Vertex-cover.

REDUCED SOLUTION GRAPH OF VERTEX-COVER
To study the solution space of Vertex-cover, the leaf removal [29] should be mentioned as inspiration. Given a graph G, a leaf is a couple of nodes {v, w} in which the first one has degree 1 and the second one is the only neighbor of it. Here, node v is a pendant point in the graph, node w acts as a petiole, and for the same petiole there may be more than one pendant points connecting it. To define the leaf removal, if the nodes pair {v, w} is a leaf in graph G, remove the two nodes with the edges touching them. It is very interesting that the leaf removal process can destroy all the leaves in graph G and can produce new leaves for the rest graph. In Figure 1, a leaf removal process for a simple graph is shown.
By this leaf removal process, we can find that there exist some graphs which have no leaf removal core until the termination of this process, which means that each node belongs to a leaf in the graph. For the Vertex-cover of these graphs, to obtain the minimum vertex cover for the graph, there is one and only one node should be covered for each leaf. By the results in [29], a trivial minimum vertex cover can be obtained by making all the petioles covered with all the pendant points uncovered in different levels of leaves, e.g., making the nodes {c, e, g} or {c, e, f } covered and the rest uncovered leads to minimum vertex covers. Here, we will take use of this trivial solution to construct a relationship between/among nodes in a leaf.
In Figure 1 core for the given graph, and whether this expression is also effective for general graphs with leaf-removal cores and how to obtain the reduced solution graph of Vertex-cover will be discussed in the following.
In order to have a convenient analysis of the reduced solution graph, the leaf-removal [29] sequence is very important. Here, we take advantage of the sequence of the leaf removal to define the rank of each node: Step 1: All the pendant points in the graph are assigned to sequence order/rank 1, and their neighbors (the petioles) have rank 2; Step 2: Remove the leaves with edges connecting them from the graph. After the leaf removal, all the new produced pendant points are assigned to rank 3, and their corresponding petioles have rank 4; Step 3: Repeat the steps 1-2 and assign increasing ranks until their are no new leaves produced. If there is still a leaf-removal core after the above two steps, assign the nodes in the core with ranks according to their already ranked neighbors by gradually increase.

VERTEX-COVER
In this section, we concern on achieving the reduced solution graph S(G) by determining the states of the nodes one by one following the leaf removal sequence/ranks. This process is fulfilled by a method similar to the cavity method, and for each node its state is determined by the local environment of itself. Considering a new node i connected to a graph G with k edges, the newly produced graph is denoted by G ′ . For the neighborhood of node i, there are three kinds of neighbors: positively frozen ones, negatively frozen ones and unfrozen ones.

Local evolution of mutual-determinations and backbones
In this subsection, we consider the different local environments of a new node i, and investigate the state determination and evolution of it and associated nodes. Taking advantage of the analysis in [18], we first study the following four cases: • Case A: only one of its neighbors is positively frozen in G; some other neighbors are unfrozen nodes which can take spin value −1 simultaneously.
In case A, energy increase is unavoidable when node i is added. When σ i takes value −1 (covered), its neighbors of nodes are free to take their spin values in the original G, and new covers of the new graph G ′ come out with the lowest energy; when σ i takes value 1, the positively frozen neighbor should be changed to an unfrozen node taking −1 now, e.g., adding the node e to the subgraph of {a, b, c, d} leads a mutual-determination of {d, e} in Figure 1 and the above subgraph in Figure 3 also show this process. Then, mutual-determination of the new added i with the original positively frozen node j is formed.
• Case B: there are more than two neighbors which are positively frozen.
In case B, energy increase is unavoidable when node i is added. To obtain a coverage of the new graph G ′ from the original one G, the new added node i must be covered without other choice. Then, node i is negatively frozen. (There will be a supplementary and additional adjustment for this case in the following case E when the positively frozen neighbors have some common properties.) • Case C: there is no neighbor which is positively frozen, but all the unfrozen neighbors can take spin value −1 simultaneously.
In case C, energy increase is avoidable when node i is added, and the new added node i should be uncovered. When σ i takes value +1, all the unfrozen neighbors should take −1 simultaneously. Then, by the mutual-determinations and coverage of each edge in the reduced solution graph S(G), that these unfrozen neighbors change to be negatively frozen will lead a number of associated unfrozen nodes to be frozen.
• Case D: there is at least one pair of unfrozen neighbors that can not take spin value −1 simultaneously.
In case D, as the two neighbors can not take −1 simultaneously, energy increase is inevitable. Then, the new added variable i should take −1 to ensure the coverage. However, for the incompatible cycles (like that in the below subgraph of Figure 3), making any other node except i frozen to −1 and the rest unfrozen nodes connected by alternatively existing double edges will have the same effect and ensure the coverage. Thus, in case D freezing the new added node i to −1 will reduce the whole solution space to a partial solution subspace.
Nevertheless, as takeing any one to be frozen on the incompatible cycle leads to a solution subspace with the same size, we have the convenient way to make i negative backbone.
By the above analysis, the incompatible cycle in the reduced solution graph makes a possible inaccurate choice of the negatively frozen backbone. Thus, the hardness of solving Vertex-cover mainly stems from the incompatible cycles.
There exists an interesting entanglement between case A and case C. In case C, some added node i 1 has a positively frozen state, its unfrozen neighbors are forced to be frozen with some associated nodes. In case A, if some new added node i 2 is connected to i 1 and forms mutual-determination with i 1 by the rule of case A, the nodes that have been frozen by i 1 should be released to their original unfrozen state. To fulfill this releasing steps, an additional mark should be sticken to the node number, e.g., a node (4, 7) means that the node 4 has been frozen by the operation of adding node 7. Indeed, this freezing influence happens only in case C with node 7 positively frozen. Then, if the state of node 7 is changed to be unfrozen by adding a new node 8 in case A, we can release all the nodes with mark ( * , 7) and change the corresponding numbers to ( * , 0), in which 0 means the state of the node is unfrozen. This operation is named releasing operation.
For the releasing operation, there is a special case should be considered for the node adding process: • Case E: there are more than two neighbors which are positively frozen and have the same additional mark, and the unfrozen neighbors can take spin value −1 simultaneously.
This case is a supplementary and additional adjustment of case B.
In this case, the current node should form mutual-determinations with the positively frozen nodes whose additional marks are the same, and the releasing operation is operated for these positively frozen neighbors (a simple example can be seen in the below subgraph of Figure 7).

Some supplementing techniques for the states evolution
In the releasing operation for case A, to avoid some possible mistakes, a checking technique should be considered. When releasing the negatively frozen backbones in the releasing operations for case A, its local environment should be considered, and if there are positively frozen neighbors for the current negatively frozen backbone whose additional mark is not same as itself, the releasing process should be stopped (e.g., the node b in the process of subgraphs (3)(4) in Figure 2).
Be specific to this checking item, after the operations of case A-D, a rechecking technique additional mark with it (e.g., the node b in the process of subgraphs (4)(5) in Figure 2).
At last, by the process of above analysis, a complicated structure-odd cycles on the reduced solution graph could come into appearance, which makes conflictions for the relations among the unfrozen nodes. For the example in Figure 2, the subgraphs (1-7) provide the process from the original graph to the reduced solution graph by adding the nodes one by one using our techniques above, but unfortunately the unfrozen nodes b, c, d, e, f, g, h in subgraph (7) form an odd cycle. In the odd cycle, we find that any node except b taking any value will force the node b to be negatively frozen, and it is an incompatible cycle. To break this disharmony, the only way is to change the state of b to be negative backbone and make corresponding changes for its neighbors with lower ranks (e.g., the process from subgraph (7) to (8) in Figure 2). This technique is named odd cycles breaking.

Global characteristics of mutual-determinations
In the following, we will have an explicit discussion of the mutual-determinations and unfrozen nodes structure of Vertex-cover. As mentioned above, if some node i forms mutualdetermination with a node j, i.e., σ i = −1 forces σ j to take +1, correspondingly by the Vertex-cover, we have that σ i = +1 requires σ j = −1 to satisfy the coverage. If a node j forms a mutual-determination chain with some other nodes j 0 , j 1 , · · · , j k , a possible way is that the edges (j, j 0 ), (j 1 , j 2 ), · · · on the reduced solution graph are all double edges, i.e., all these pairs of nodes form mutual-determinations, which is shown in the Cycle 2-Compatible Cycle in Figure 3. When the node j takes vale −1 (covered), the nodes j 0 , j 2 , · · · , j 2l , · · · must take +1 by the mutual-determination relations and coverage of the edges connecting them, and the nodes j 1 , j 3 , · · · , j 2l+1 , · · · must take −1. Therefore, the alternatively existing double edges on the reduced solution graph lead to the emergence of the strong correlation for nodes of long distance.
Without confusion, we neglect the backbones in the reduced solution graph but keep the the increasing of the number of nodes and edges, the unfrozen nodes with double edges in the reduced solution graph may connect together, and form cycles and even giant connected component. Especially, for random graphs, the cycles connected by unfrozen nodes in the reduced solution graph must be with size of O(logN). Therefore, if the unfrozen nodes connect together to form a giant connected component [28], some of them taking value −1 will cause a percolation phenomenon [27] that many other nodes (O(N)) in this giant connected component will be forced to be frozen. As a result, the long-range correlation phenomenon emerges. In the work of Zhou [18], the long-range correlation of Vertex-cover for random graph appears at c = e. Indeed, by the literature of statistical mechanics, the existence of long-range correlation has close connection with the replica symmetric breaking of the solution space. As the correlation is formed by mutual-determinations, the long-range correlation can also provide an explicit explanation of the clustering phenomenon of solution space.
By the emergency of the long-range correlation nodes, the local environment becomes much more complicated. As unfrozen neighbors of the new added node i can be connected together by other unfrozen nodes, their values can not be assigned arbitrarily. In Figure   3, a schematic view of the compatible and incompatible cycles of unfrozen nodes is shown.
In Cycle 1, the unfrozen nodes k 1 , k 2 are connected by unfrozen nodes with alternatively existing double edges, and it is easy to find that the nodes k 1 , k 2 form a long-range correlation relation and can not take spin value −1 simultaneously. To the contrary, in the compatible Cycle 2, though the relation between j, j m−1 is also long-range correlation, they can take spin value −1 simultaneously by the mutual-determination chain in Cycle 2.

MUTUAL-DETERMINATION AND BACKBONE EVOLUTION ALGORITHM FOR VERTEX-COVER
In this section, we will introduce an algorithm for solving Vertex-cover based on case A-E and the node ranks. By the analysis in case A, B, C, D, E, we consider to update the state of the original graph G(N − 1) after adding a new node i. As the node states are classified by mutual-determinations and backbones, we can get an algorithm to find the reduced solution graph R(G) of Vertex-cover, this algorithm is named Mutual-determination and Backbone Evolution Algorithm, shown as follows: Let's take G[v] as an induced subgraph of original graph G by adding node v and To reflect the solution space structures of Vertex-cover, the ratios of negatively frozen backbone and positively frozen backbones are detected by the algorithm, in which one is monotone increasing and the other is monotone decreasing. In Figure 4, the ratios of the backbones are shown by the solid triangles, and the unfrozen nodes have its ratio with the residual part of one. Our results on the frozen nodes in one macroscopic state is higher than that in [17] mainly be the freezing influence. Besides, in Figure 5, the coverage of the Vertexcover which is the size of the minimal vertex-cover is approximated by our algorithm, which is Evolution Algorithm when c < e in the next section, our numerical results should be exact ones for the corresponding interval on random graphs.
As a comparison to the complete algorithm and the exact coverage, some experiments are made to verify the performance of the Mutual-determination and Backbone Evolution Algorithm which is an incomplete algorithm. In Figure 6, average Error of minimal vertex cover between experimental and exact results are plotted to provide the difference between the exact results and our results on the coverage, and it is evident to see that these differences are not very big and have their scales no more than 0.04 for c = 2, 4, 6 with increasing sizes.

Mutual-determination and Backbone Evolution Algorithm on some examples
To detect the reduced solution graph and provide a primary analysis of efficiency of our algorithm on the leaf-removal core, we will discuss the Vertex-cover on the complete graphs and cycles with even number of nodes for inspiration.
For the complete graphs, the process of our algorithm to obtain the reduced solution graph is rather simple: when the second node is added with an edge (subgraph (1) in Figure 7), the mutual-determination emerges; for the following added nodes, their local environment satisfies the case D and they can only be negative backbones. This process is shown in Figure 7 by a typical graph K 5 . It is easy to know that for the complete graph K N there must be N − 1 nodes be covered, and our results of reduced solution graph correspond to a solution subspace of the Vertex-cover of K N . The whole solution space possesses N solutions and by our algorithm we can obtain 2 solutions. Therefore, the mutual-determination and Backbone Evolution Algorithm is an incomplete algorithm for the solution space, but it may be efficient for finding one solution of Vertex-cover. Certainly, as analyzed in the above section, the incompatible cycles of the unfrozen node will bring the intrinsic difficulty for solving it and our algorithm can only obtain some approximated solutions for the original problem.
Then, the cycles C 2N with even number of nodes are considered. The process of our algorithm to obtain its reduced solution graph is a regular process: when odd number of nodes are added, there are no unfrozen nodes in the reduced solution graph; when even number of nodes are added, the releasing operations should be considered and all the nodes are unfrozen with double edges/mutual-determinations alternatively connected together; for the last node, it connects with two positively frozen nodes which have the same additional mark 2N − 1, and by the case E the last node forms mutual-determination with node 2N − 1 and the rest are released. The whole process is schematically shown in the lower subgraphs (a − d) in Figure 7 by a typical graph C 4 . Thus, the solution space of C 2N can be obtained, and it is easy to verify that the result is strict by our algorithm.

ANALYSIS OF MUTUAL-DETERMINATION AND BACKBONE EVOLUTION ALGORITHM FOR VERTEX-COVER
The Mutual-determination and Backbone Evolution Algorithm aims to obtain the whole solution space, and it is easy to find that it is an algorithm of polynomial time. As the Vertexcover problem is a typical NP-complete problem, this algorithm can not be a complete one and will lose its efficiency in some case. In this section, some detailed analysis on the algorithm will be provided.

The time complexity of Mutual-determination and Backbone Evolution Algorithm
By the algorithm in the above section, the process of determining the ranks of the nodes in the graph is intrinsically a leaf removal process, and it will cost at most O(N) steps to obtain the whole ranks of all the nodes.
By considering the nodes sequentially according to their ranks, when adding a new node to the original graph, first we should consider its local environment, which will cost at most constant C steps for random graph. Then, in different cases A-E, there may be additional time cost. In case B and D, the current state of the new added node is only determined by its neighbors and it causes no influence to others; In case C, the freezing of the current node will cause an influence to the unfrozen neighbors and those related to them, and thus the At last, considering case D, when the leaf-removal core is null, this case can be reduced to the odd cycle breaking, and it will bring the kernel difficulty when the leaf-removal core exists.
Therefore, the reduced solution graph obtained by our algorithm can reveals the exact solution space when there is no leaf-removal core.
By the above analysis, we have shown that the Mutual-determination and Backbone

22
Evolution Algorithm is strict when there is no leaf-removal core in the graph. By the results in [29], there is no leaf-removal core in the random graph with high probability when the average degree c is less than e. Then, our algorithm is strict with high probability when c < e.

Cycles in the reduced solution graph
The even and odd cycles of unfrozen nodes will be analyzed in this subsection. In this right subgraph of Figure  determinations, e.g., subgraph (7) of Figure 2, what we can do is to perform the odd cycle breaking, which keeps the strictness of our algorithm.
Unfortunately, there is the other way to produce an odd cycle of alternative mutualdeterminations, just like the Incompatible Cycle in the below subgraph of Figure 3. This kind of odd cycle structure emerges when the leaf-removal core exists and is hard to be broken for the lowest energy configuration of Vertex-cover. As the incompatible cycle brings obstacle for obtaining the real reduced solution graph, changing any unfrozen node on it to be negatively frozen is a possible choice for the reduced solution graph. In our algorithm, we can only choose one way to proceed, which makes the solution space collapse to a subspace.
Many steps of the collapsing may lead to unnecessary energy increase and superfluous cover of the graph.
In fact, we can keep all the incompatible cycles of alternative mutual-determinations without breaking choices for each step in the leaf-removal core and deal with them for the final reduced solution graph. All the backbones have no influence on the solution space, but breaking the incompatible cycles of alternative mutual-determinations on the reduced solution graph is an urgent task for achieving the proper solution subspaces. Many these incompatible cycles are coupled together and should be broken by making some nodes on 23 them negatively frozen. The fewer the number of negatively frozen nodes are chosen, the better covers we can obtain. Therefore, this problem can be reduced to the MAX-CUT [30] problem for the unfrozen nodes of the reduced solution graph. By the results of MAX-CUT, breaking the edges of unfrozen nodes which do not belong to the max-cut will lead to totaly compatible cycles. However, the MAX-CUT problem is also a NP-complete problem which is hard to solve.

CONCLUSION AND DISCUSSION
A new solution space structure, mutual-determination between unfrozen nodes is defined and discovered in some detailed case of the Vertex-cover. Based on the mutualdeterminations and backbones, we construct the reduced solution graph to reveal the solution space of Vertex-cover. And, inspired by the leaf removal process and introducing node ranks, a dynamical process for the evolution of the node states is studied to achieve the current states of nodes in the reduced solution graph. Combing the mutual-determinations, backbones and the node ranks, an algorithm named Mutual-determination and Backbone Evolution Algorithm is proposed to obtained the accurate reduced solution graph. To ensure the accuracy of the algorithm, the releasing operations, checking and rechecking techniques and odd cycles breaking operation are defined by considering the influence propagation.
Then, the numerical results and some examples are given to verify the validity of the algorithm. Besides, we have proved that this algorithm is an O(N 2 ) algorithm and performs strict when there is no leaf-removal core for the graph. the influence of incompatible cycles of unfrozen nodes to the algorithm is given, which can be reduced to MAX-CUT problem.
The Mutual-determination and Backbone Evolution Algorithm can be applied to a wide range of graphs. Though the difficulties are brought to by the incompatible cycles in case D on the reduced solution graph, choosing proper strategies to break the cycles will be helpful to obtain a solution subspace, which will be beneficial to solve the Vertex-cover problem in different topologies. Besides, in order to break the incompatible cycles of unfrozen nodes in case D on the reduced solution graph, we should design better heuristic strategies to check the key unfrozen nodes on it, such as taking advantage of the centrality or clustering coefficient [33,34]. However, as the intrinsic character of Vertex-cover is NP-complete, the Mutual-determination and Backbone Evolution Algorithm will still be an approximated one, and what we aim at is to improve the accuracy of solving different graphs of Vertex-cover.
The reduced solution graph of Mutual-determination and Backbone Evolution Algorithm can correspond to the whole solution space of Vertex-cover in some cases, which is a great help to count the number of solutions. Similar as the #CSP [31,32], the #Vertex-cover can be analyzed based on the reduced solution graph. However, calculating the exact entropy of the solution space needs a much detailed analysis of the constructions of the reduced solution graph and there should be many techniques to be introduce on counting the solutions on the reduced solution graph. Besides, the reduced solution graph can help explicitly determine the role of every node and calculate the partition functions and marginal probabilities of the nodes/variables. Some of the related results will be proceeded in our future work.
The principal of our algorithm is related to the replica symmetry theory but not restrict to. Most of recent algorithms solving combinatorial optimization problems always concentrate to find one solution, such as the searching algorithms, heuristic algorithms and even the Belief/Survey Propagation algorithm [15,21]. They assign values to the nodes/variables according to some strategies and do backtracking to reach the optimal solution, or determine