# Statistical sentiment analysis performance in Opinum

Boyan Bonev, Gema Ramírez-Sánchez, Sergio Ortiz Rojas  Prompsit Language
Engineering
Avenida Universidad, s/n. Edificio Quorum III.
03202 Elche, Alicante (Spain)
<EMAIL_ADDRESS>
###### Abstract

The classification of opinion texts in positive and negative is becoming a
subject of great interest in sentiment analysis. The existence of many labeled
opinions motivates the use of statistical and machine-learning methods. First-
order statistics have proven to be very limited in this field. The Opinum
approach is based on the order of the words without using any syntactic and
semantic information. It consists of building one probabilistic model for the
positive and another one for the negative opinions. Then the test opinions are
compared to both models and a decision and confidence measure are calculated.
In order to reduce the complexity of the training corpus we first lemmatize
the texts and we replace most named-entities with wildcards. Opinum presents
an accuracy above 81% for Spanish opinions in the financial products domain.
In this work we discuss which are the most important factors that have an
impact on the classification performance.

###### keywords:

sentiment analysis , opinion classification , language model

††journal: arXiv

##  1 Introduction

Most of the texts written by humans reflect some kind of sentiment. The
interpretation of these sentiments depend on the linguistic skills and
emotional intelligence of both the author and the reader, but above all, this
interpretation is subjective to the reader. They don’t really exist in a
string of characters, for they are subjective states of mind. Therefore
sentiment analysis is a prediction of how most readers would react to a given
text.

There are texts which intend to be objective and texts which are intentionally
subjective. The latter is the case of opinion texts, in which the authors
intentionally use an appropriate language to express their positive or
negative sentiments about something. In this paper we work on the
classification of opinions in two classes: those expressing positive sentiment
(the author is in favour of something) and those expressing negative
sentiment, and we will refer to them as positive opinions and negative
opinions.

Sentiment analysis is possible thanks to the opinions available on-line. There
are vast amounts of text in fora, user reviews, comments in blogs and social
networks. It is valuable for marketing and sociological studies to analyse
these freely available data on some definite subject or entity. Some of the
texts available do include opinion information like stars, or recommend-or-
not, but most of them do not. A good corpus for building sentiment analysis
systems would be a set of opinions separated by domains. It should include
some information about the cultural origin of authors and their job, and each
opinion should be sentiment-evaluated not only by its own author, but by many
other readers as well. It would also be good to have a marking of the
subjective and objective parts of the text. Unfortunately this kind of corpora
are not available at the moment.

In the present work we place our attention at the supervised classification of
opinions in positive and negative. Our system, which we call Opinum111An
Opinum installation can be tested from a web interface at
http://aplica.prompsit.com/en/opinum, is trained from a corpus labeled with a
value indicating whether an opinion is positive or negative. The corpus was
crawled from the web and it consists of a 160MB collection of Spanish opinions
about financial products. Opinum’s approach is general enough and it is not
limited to this corpus nor to the financial domain.

There are state-of-the-art works on sentiment analysis which care about
differentiating between the objective and the subjective part of a text. For
instance, in the review of a film there is an objective part and then the
opinion (Raaijmakers et al. (2008)). In our case we work directly with opinion
texts and we do not make such difference. We have noticed that in customer
reviews, even when stating objective facts, some positive or negative
sentiment is usually expressed.

Many works in the literature of sentiment analysis take lexicon-based
approaches, like Taboada et al. (2011). For instance Hu and Liu (2004); Blair-
Goldensohn et al. (2008) use WordNet to extend the relation of positive and
negative words to other related lexical units. However the combination of
which words appear together may also be important and there are comparisons of
different Machine learning approaches (Pang et al. (2002)) in the literature,
like Support Vector Machines, k-Nearest Neighbours, Naive-Bayes, and other
classifiers based on global features. In the work of Mcdonald et al. (2007),
structured models are used to infer the sentiment from different levels of
granularity. They score cliques of text based on a high-dimensional feature
vector.

In the Opinum approach we score each sentence based on its $n$-gram
probabilities. For a complete opinion we sum the scores of all its sentences.
Thus, if an opinion has several positive sentences and it finally concludes
with a negative sentence which settles the whole opinion as negative, Opinum
would probably fail. The $n$-gram sequences are good at capturing phrasemes
(multiwords), the motivation for which is stated in Section 2. Basically,
there are phrasemes which bear sentiment. They may be different depending on
the domain and it is recommendable to build the models with opinions belonging
to the target domain, for instance, financial products, computers, airlines,
etc. A study of domain adaptation for sentiment analysis is presented in the
work of Blitzer et al. (2007). In Opinum different classifiers would be built
for different domains. Building the models does not require the aid of
experts, only a labeled set of opinions is necessary. Another contribution of
Opinum is that it applies some simplifications on the original text of the
opinions for improving the performance of the models.

In the remainder of the paper we first state the motivation of our approach in
Section 2, then in Section 3 we describe in detail the Opinum approach. In
Section 4 we present our experiments with Spanish financial opinions. In
Section 5 we discuss which are the most important factors that have an effect
on the classification performance. Finally we state some conclusions and
future work in Section 6.

##  2 Hypothesis

When humans read an opinion, even if they do not understand it completely
because of the technical details or domain-specific terminology, in most cases
they can notice whether it is positive or negative. The reason for this is
that the author of the opinion, consciously or not, uses nuances and
structures which show a positive or negative feeling. Usually, when a user
writes an opinion about a product, the intention is to communicate that
subjective feeling, apart from describing the experience with the product and
giving some technical details.

The hypothesis underlying the traditional keyword or lexicon-based approaches
(Blair-Goldensohn et al. (2008); Hu and Liu (2004)) consist in looking for
some specific positive or negative words. For instance, “great” should be
positive and “disgusting” should be negative. Of course there are some
exceptions like “not great”, and some approaches detect negation to invert the
meaning of the word. More elaborate cases are constructions like “an offer you
can’t refuse” or “the best way to lose your money”.

There are domains in which the authors of the opinions might not use these
explicit keywords. In the financial domain we can notice that many of the
opinions which express the author’s insecurity are actually negative, even
though the words are mostly neutral. For example, “I am not sure if I would
get a loan from this bank” has a negative meaning. Another difficulty is that
the same words could be positive or negative depending on other words of the
sentence: “A loan with high interests” is negative while “A savings account
with high interests” is positive. In general more complex products have more
complex and subtle opinions. The opinion about a cuddly toy would contain many
keywords and would be much more explicit than the opinion about the conditions
of a loan. Even so, the human readers can get the positive or negative feeling
at a glance.

The hypothesis of our approach is that it is possible to classify opinions in
negative and positive based on canonical (lemmatized) word sequences. Given a
set of positive opinions $\mathbf{O}^{p}$ and a set of negative opinions
$\mathbf{O}^{n}$, the probability distributions of their $n$-gram word
sequences are different and can be compared to the $n$-grams of a new opinion
in order to classify it. In terms of statistical language models, given the
language models $\mathit{M}^{p}$ and $\mathit{M}^{n}$ obtained from
$\mathbf{O}^{p}$ and $\mathbf{O}^{n}$, the probability
$p^{p}_{o}=P(o|\mathbf{O}^{p})$ that a new opinion would be generated by the
positive model is smaller or greater than the probability
$p^{n}_{o}=P(o|\mathbf{O}^{N})$ that a new opinion would be generated by the
negative model.

We build the models based on sequences of canonical words in order to simplify
the text, as explained in the following section. We also replace some named
entities like names of banks, organizations and people by wildcards so that
the models do not depend on specific entities.

##  3 The Opinum approach

The proposed approach is based on $n$-gram language models. Therefore building
a consistent model is the key for its success. In the field of machine
translation a corpus with size of 500MB is usually enough for building a
$5$-gram language model, depending on the morphological complexity of the
language.

In the field of sentiment analysis it is very difficult to find a big corpus
of context-specific opinions. Opinions labeled with stars or a
positive/negative label can be automatically downloaded from different
customers’ opinion websites. The sizes of the corpora collected that way range
between 1MB and 20MB for both positive and negative opinions.

Such a small amount of text would be suitable for bigrams and would capture
the difference between “not good” and “really good”, but this is not enough
for longer sequences like “offer you can’t refuse”. In order to build
consistent $5$-gram language models we need to simplify the language
complexity by removing all the morphology and replacing the surface forms by
their canonical forms. Therefore we make no difference between “offer you
can’t refuse” and “offers you couldn’t refuse”.

We also replace named entities by wildcards: person_entity,
organization_entity and company_entity. Although these replacements also
simplify the language models to some extent, their actual purpose is to avoid
some negative constructions to be associated to concrete entities. For
instance, we do not care that “do not trust John Doe Bank” is negative,
instead we prefer to know that “do not trust company_entity” is negative
regardless of the entity. This generality allows us to better evaluate
opinions about new entities. Also, in the cases when all the opinions about
some entity E1 are good and all the opinions about some other entity E2 are
bad, entity replacement prevents the models from acquiring this kind of bias.

Following we detail the lemmatization process, the named entities detection
and how we build and evaluate the positive and negative language models.

###  3.1 Lemmatization

Working with the words in their canonical form is for the sake of generality
and simplification of the language model. Removing the morphological
information does not change the semantics of most phrasemes (or multiwords).

There are some lexical forms for which we keep the surface form or we add some
morphological information to the token. These exceptions are the subject
pronouns, the object pronouns and the possessive forms. The reason for this is
that for some phrasemes the personal information is the key for deciding the
positive or negative sense. For instance, let us suppose that some opinions
contain the sequences

$\displaystyle o_{t}$ $\displaystyle=$ $\displaystyle\text{``They made money
from me''},$ $\displaystyle o_{i}$ $\displaystyle=$ $\displaystyle\text{``I
made money from them''}.$

Their lemmatization, referred to as $\mathcal{L}_{0}(\cdot)$, would be222The
notation we use here is for the sake of readability and it slightly differs
from the one we use in Opinum.

$\displaystyle\mathcal{L}_{0}(o_{t})=\mathcal{L}_{0}(o_{i})=\text{``SubjectPronoun
make money}$ $\displaystyle\text{ from ObjectPronoun''},$

Therefore we would have equally probable $P(o_{t}|M^{p})=P(o_{i}|M^{p})$ and
$P(o_{t}|M^{n})=P(o_{i}|M^{n})$, which does not express the actual sentiment
of the phrasemes. In order to capture this kind of differences we prefer to
have

$\displaystyle\mathcal{L}_{1}(o_{t})$ $\displaystyle=$ “SubjectPronoun_3p make
money $\displaystyle\text{ from ObjectPronoun\\_1p''},$
$\displaystyle\mathcal{L}_{1}(o_{i})$ $\displaystyle=$ “SubjectPronoun_1p make
money $\displaystyle\text{ from ObjectPronoun\\_3p''}.$

The probabilities still depend on how many times do these lexical sequences
appear in opinions labeled as positive or negative, but with
$\mathcal{L}_{1}(\cdot)$ we would have that

$\displaystyle P(o_{t}|M^{p})<P(o_{i}|M^{p}),$ $\displaystyle
P(o_{t}|M^{n})>P(o_{i}|M^{n}),$

that is, $o_{i}$ fits better the positive model than $o_{t}$ does, and vice
versa for the negative model.

In our implementation lemmatization is performed with Apertium, which is an
open-source rule-based machine translation engine. Thanks to its modularized
architecture (described in Tyers et al. (2010)) we use its morphological
analyser and its part-of-speech disambiguation module in order to take one
lexical form as the most probable one, in case there are several possibilities
for a given surface. Apertium currently has morphological analysers for 30
languages (most of them European), which allows us to adapt Opinum to other
languages without much effort.

###  3.2 Named entities replacement

The corpora with labeled opinions are usually limited to a number of
enterprises and organizations. For a generalization purpose we make the texts
independent of concrete entities. We do make a difference between names of
places, people and organizations/companies. We also detect dates, phone
numbers, e-mails and URL/IP. We substitute them all by different wildcards.
All the rest of the numbers are substituted by a “Num” wildcard. For instance,
the following subsequence would have a $\mathcal{L}_{2}(o_{e})$ lemmatization
+ named entity substitution:

$\displaystyle o_{e}=$ “Joe bought 300 shares of Acme Corp. in 2012”
$\displaystyle\mathcal{L}_{2}(o_{e})=$ “Person buy Num share of Company in
Date”

The named entity recognition task is integrated within the lemmatization
process. We collected a list of names of people, places, companies and
organizations to complete the morphological dictionary of Apertium. The
morphological analysis module is still very fast, as the dictionary is first
compiled and transformed to the minimal deterministic finite automaton. For
the dates, phone numbers, e-mails, IP and URL we use regular expressions which
are also supported by the same Apertium module.

Regarding the list of named entities, for a given language (Spanish in our
experiments) we download its Wikipedia database which is a freely available
resource. We heuristically search it for organizations, companies, places and
people. Based on the number of references a given entity has in Wikipedia’s
articles, we keep the first 1.500.000 most relevant entities, which cover the
entities with 4 references or more (the popular entities are referenced from
tens to thousands of times).

Finally, unknown surface forms are replaced by the “Unknown” lemma (the known
lemmas are lowercase). These would usually correspond to strange names of
products, erroneous words and finally to words which are not covered by the
monolingual dictionary of Apertium. Therefore our approach is suitable for
opinions written in a rather correct language. If unknown surfaces were not
replaced, the frequently misspelled words would not be excluded, which is
useful in some domains. This is at the cost of increasing the complexity of
the model, as all misspelled words would be included. Alternatively, the
frequently misspelled words could be added to the dictionary.

###  3.3 Language models

The language models we build are based on $n$-gram word sequences. They model
the likelihood of a word $w_{i}$ given the sequence of $n-1$ previous words,
$P(w_{i}|w_{i-(n-1)},\ldots,w_{i-1})$. This kind of models assume independence
between the word $w_{i}$ and the words not belonging to the $n$-gram,
$w_{j},\,j<i-n$. This is a drawback for unbounded dependencies but we are not
interested in capturing the complete grammatical relationships. We intend to
capture the probabilities of smaller constructions which may hold
positive/negative sentiment. Another assumption we make is independence
between different sentences.

In Opinum the words are lemmas (or wildcards replacing entities), and the
number of words among which we assume dependence is $n=5$. A maximum $n$ of 5
or 6 is common in machine translation where huge amounts of text are used for
building a language model (Koehn et al. (2007)). In our case we have at our
disposal a small amount of data but the language is drastically simplified by
removing the morphology and entities, as previously explained. We have
experimentally found that $n>5$ does not improve the classification
performance of lemmatized opinions and could incur over-fitting.

In our setup we use the IRSTLM open-source library for building the language
model. It performs an $n$-gram count for all $n$-grams from $n=1$ to $n=5$ in
our case. To deal with data sparseness a redistribution of the zero-frequency
probabilities is performed for those sets of words which have not been
observed in the training set $\mathcal{L}(\mathbf{O})$. Relative frequencies
are discounted to assign positive probabilities to every possible $n$-gram.
Finally a smoothing method is applied. Details about the process can be found
in Federico and Cettolo (2007). Another language model approach based on
$n$-grams was reported in Cui et al. (2006), where they used the CMU-Cambridge
Language Modeling Toolkit on the original texts.

For Opinum we run IRSTLM twice during the training phase: once taking as input
the opinions labeled as positive and once taking the negatives:

$\displaystyle\mathit{M^{p}}$ $\displaystyle\leftarrow$
$\displaystyle\text{Irstlm}\left(\mathcal{L}\left(\mathbf{O}^{p}\right)\right)$
$\displaystyle\mathit{M^{n}}$ $\displaystyle\leftarrow$
$\displaystyle\text{Irstlm}\left(\mathcal{L}\left(\mathbf{O}^{n}\right)\right)$

These two models are further used for querying new opinions on them and
deciding whether it is positive or negative, as detailed in the next
subsection.

###  3.4 Evaluation and confidence

In the Opinum system we query the $\mathit{M^{p}},\mathit{M^{n}}$ models with
the Heafield (2011) KenLM open-source library because it answers the queries
very quickly and has a short loading time, which is suitable for a web
application. It also has an efficient memory management which is positive for
simultaneous queries to the server.

The queries are performed at sentence level. Each sentence $s\in o_{t}$ is
assigned a score which is the log probability of the sentence being generated
by the language model. The decision is taken by comparing its scores for the
positive and for the negative models. For a given opinion $o_{t}$, the log-
probability sums can be taken:

$d_{o_{t}}=\sum_{s\in o_{t}}\log P(s|\mathit{M}^{p})-\sum_{s\in o_{t}}\log
P(s|\mathit{M}^{n})\begin{array}[]{c}\\\ \gtrless\\\ ?\end{array}0$

If this difference is close to zero, $|d_{o_{t}}|/w_{o_{t}}<\varepsilon_{0}$,
it can be considered that the classification is neutral. The number of words
$w_{o_{t}}$ is used as a normalization factor. If it is large,
$|d_{o_{t}}|/w_{o_{t}}>\varepsilon_{1}$, it can be considered that the opinion
has a very positive or very negative sentiment. Therefore Opinum classifies
the opinions with qualifiers: very/somewhat/little positive/negative depending
on the magnitude $|d_{o_{t}}|/w_{o_{t}}$ and $\operatorname{sign}(d_{o_{t}})$,
respectively.

The previous assessment is also accompanied by a confidence measure given by
the level of agreement among the different sentences of an opinion. If all its
sentences have the same positivity/negativity, measured by
$\operatorname{sign}(d_{s_{j}}),\,s_{j}\in o$, with large magnitudes then the
confidence is the highest. In the opposite case in which there is the same
number of positive and negative sentences with similar magnitudes the
confidence is the lowest. The intermediate cases are those with sentences
agreeing in sign but some of them with very low magnitude, and those with most
sentences of the same sign and some with different sign. We use Shannon’s
entropy measure $H(\cdot)$ to quantify the amount of disagreement. For its
estimation we divide the range of possible values of $d$ in $B$ ranges,
referred to as bins:

$H_{o_{t}}=\displaystyle\sum_{b=1}^{B}p(d_{b})\log\dfrac{1}{p(d_{b})}.$

The number of bins should be low (less than 10), otherwise it is difficult to
get a low entropy measure because of the sparse values of $d_{b}$. We set two
thresholds $\eta_{0}$ and $\eta_{1}$ such that the confidence is said to be
high/normal/low if $H_{o_{t}}<\eta_{0}$, $\,\eta_{0}<H_{o_{t}}<\eta_{1}$ or
$H_{o_{t}}>\eta_{1}$, respectively

The thresholds $\varepsilon$, $\eta$ and the number of bins $B$ are
experimentally set. The reason for this is that they are used to tune
subjective qualifiers (very/little, high/low confidence) and will usually
depend on the training set and on the requirements of the application. Note
that the classification in positive or negative sentiment is not affected by
these parameters. From a human point of view it is also a subjective
assessment but in our setup it is looked at as a feature implicitly given by
the labeled opinions of the training set.

##  4 Experiments

Similar words, different meaning |
---|---
Original Spanish text | Meaning in English | Result
| “Al tener la web, no pierdes
---
el tiempo por teléfono.”
| As you have the website you
---
don’t waste time on the phone.
Positive
| “En el teléfono os hacen perder
---
el tiempo y no tienen web.”
| They waste your time on the phone
---
and they don’t have a website.
Negative
| “De todas formas me
---
solucionaron el problema.”
| Anyway, they solved my problem.
---
Positive
| “No hay forma de que
---
me solucionen el problema.”
| There is no way to make them
---
solve my problem.
Negative
Table 1: Opinum for financial opinions in Spanish. Short examples of successful classification which may be attributed to the $n$-grams models (order $n=5$). These examples can be tested on-line at http://www.prompsit.com/en/opinum, in the 2012 version. A negative opinion with several sentences |
---|---
Original Spanish text | Meaning in English | Result
| “Con ENTIDAD me fue muy
---
bien.”
| I was fine with ENTITY.
---
Positive
| “Hasta que surgieron los
---
problemas.”
| Until the problems began.
---
Negative
| “Por hacerme cliente me
---
regalaban 100 euros.”
| They gave me 100 euro for
---
becoming a client.
Positive
| “Pero una vez que eres cliente
---
no te aportan nada bueno.”
| But once you are a client, they
---
they do not offer anything good.
Negative
| “Estoy pensando cambiar de
---
banco.”
| I am considering switching to
---
another bank.
Negative
Classification of the complete opinion | Negative
Table 2: Example of an opinion with several sentences which is classified as
Negative.

In our experimental setup we have a set of positive and negative opinions in
Spanish, collected from a web site for user reviews and opinions. The opinions
are constrained to the financial field including banks, savings accounts,
loans, mortgages, investments, credit cards, and all other related topics. The
authors of the opinions are not professionals, they are mainly customers.
There is no structure required for their opinions, and they are free to tell
their experience, their opinion or their feeling about the entity or the
product. The users meant to communicate their review to other humans and they
don’t bear in mind any natural language processing tools. The authors decide
whether their own opinion is positive or negative and this field is mandatory.

The users provide a number of stars as well: from one to five, but we have not
used this information. It is interesting to note that there are 66 opinions
with only one star which are marked as positive. There are also 67 opinions
with five stars which are marked as negative. This is partially due to human
errors, a human can notice when reading them. However we have not filtered
these noisy data, as removing human errors could be regarded as biasing the
data set with our own subjective criteria.

Regarding the size of the corpus, it consists of 9320 opinions about 180
different Spanish banks and financial products. From these opinions 5877 are
positive and 3443 are negative. There is a total of 709741 words and the mean
length of the opinions is 282 words for the positive and 300 words for the
negative ones. In the experiments we present in this work, we randomly divide
the data set in 75% for training and 25% for testing. We check that the
distribution of positive and negative remains the same among test and train.

After the $\mathcal{L}_{2}(\cdot)$ lemmatization and entity substitution, the
number of different words in the data set is 13067 in contrast with the 78470
different words in the original texts. In other words, the lexical complexity
is reduced by 83%. Different substitutions play a different role in this
simplification. The “Unknown” wildcard represents a 7,13% of the original
text. Entities were detected and replaced 33858 times (7807 locations, 5409
people, 19049 companies, 502 e-mails addresses and phone numbers, 2055 URLs,
1136 dates) which is a 4,77% of the text. There are also 46780 number
substitutions, a 7% of the text. The rest of complexity reduction is due to
the removal of the morphology as explained in Subsection 3.1.

In our experiments, the training of Opinum consisted of lemmatizing and
substituting entities of the 6990 opinions belonging the training set and
building the language models. The positive model is built from 4403 positive
opinions and the negative model is built from 2587 negative opinions.
Balancing the amount of positive and negative samples does not improve the
performance. Instead, it obliges us to remove an important amount of positive
opinions and the classification results are decreased by approximately 2%.
This is why we use all the opinions available in the training set. Both
language models are $n$-grams with $n\in[1,5]$. Having a 37% less samples for
the negative opinions is not a problem thanks to the smoothing techniques
applied by IRSTLM. Nonetheless if the amount of training texts is too low we
would recommend taking a lower $n$. A simple way to set $n$ is to take the
lowest value of $n$ for which classification performance is improved.
Depending on the language model tool used, an unnecessarily high $n$ could
overfit the models. The effect of the order is further analysed in Section 5.
An example of the contribution of $n$-grams to successfully capture small
order differences is shown in Table 1.

The tests are performed with 2330 opinions (not involved in building the
models). For measuring the accuracy we do not use the qualifiers information
but only the decision about the positive or negative class. In Figure 1 we
show the scores of the opinions for the positive and negative models. The
score is the sum of scores of the sentences, thus it can be seen that longer
opinions (bigger markers) have bigger scores. Independence of the size is not
necessary for classifying in positive and negative. In the diagonal it can be
seen that positive samples are close to the negative ones, this is to be
expected: both positive and negative language models are built for the same
language. However the small difference in their scores yields an $81.98$%
success rate in the classification. An improvement of this rate would be
difficult to achieve taking into account that there is noise in the training
set and that there are opinions without a clear positive or negative feeling.
A larger corpus would also contribute to a better result. Even though we have
placed many efforts in simplifying the text, this does not help in the cases
in which a construction of words is never found in the corpus. A construction
could even be present in the corpus but in the wrong class. For instance, in
our corpus “no estoy satisfecho” (meaning “I am not satisfied”) appears 3
times among the positive opinions and 0 times among the negative ones. This
weakness of the corpus is due to sentences referring to a money back
guarantee: “si no esta satisfecho le devolvemos el dinero” which are used in a
positive context.

Figure 1:  Relation between similarity to the models (x and y axis) and the
relative size of the opinions (size of the points).

Opinum performs slightly better with long opinions, rather than short
sentences. We attribute this to the fact that in long opinions a single
sentence does not usually change much the positiveness score. For some
examples see Table 2. In long opinions every sentence is prone to show the
sentiment except for the cases of irony or opinions with an objective part.

An installation of Opinum is available on-line. It lacks usability facilities
like batch processing and files uploading because it is installed for small
test purposes. In the web interface we only provide the single opinion query
and we output the decision, the qualifiers information and the confidence
measure. For a better performance, the system can be installed in a Linux-
based machine and its scripts can be used in batch mode.

The query time of Opinum on a standard computer ranges from $1.63$ s for the
shortest opinions to $1.67$ s for those with more than 1000 words. In our
setup, most of the time is spent in loading the morphological dictionary, few
milliseconds are spent in the morphological analysis of the opinion and the
named entity substitution, and less than a millisecond is spent in querying
each model. In a batch mode, the morphological analysis could be done for all
the opinions together and thousands of them could be evaluated in seconds.

##  5 Discussion on performance

The performance of Opinum depending on the size of the opinions of the test
set is shown in Figure 2. In Figures 3, 4 and 5 the ROC curve of the
classifier shows its stability against changing the true-positive versus
false-negative rates. The success rate of Opinum is $81.98\%$, improving
significantly the $69\%$ baseline given by a classifier based on the
frequencies of single words, on the same data set. A comparison with other
methods would be a valuable source of evaluation. It is not feasible at this
moment because of the lack of free customers opinions databases and opionion
classifiers as well. However in the present work we discuss important aspects
of performance under different experimental conditions.

The first of them is the size of the opinions. In Figure 2 we show the
relation between successful and erroneous classifications. On the one hand
this figure gives an idea of the distribution of opinion lengths in the
corpus. On the other hand it shows for which opinions lengths the success rate
is better. The performance is similar for a wide range of opinion lengths:
from 2-3 sentences to opinions of several paragraphs. It can be seen that for
unusually long opinions the performance is worse. This can be attributed to
their different style. In middle sized opinions users focus on expressing a
positive or negative feeling in a few sentences, while in longer opinions they
are not so clear. One way to tackle this problem would be to take an approach
for detecting the parts of the opinion which matter for classification.
Another recommendation would be to filter the unusually short or long opinions
from the training set, or even to construct different classifiers for
different ranges of opinion lengths.

Figure 2:  Number of successful and erroneous classifications (vertical axis)
depending on the size of the test opinions (horizontal axis).

Another of the characteristics of Opinum which is worth evaluating is the
morphology substitution approach. In Figure 3 we show a comparison of the ROC
curves when using different morphological substitutions. For instance in the
classifier denoted with label A, morphology is removed but the information
about 1st, 2nd or 3rd person is kept. In B morphology is removed and named
entities (companies, people, dates, numbers) are substituted by wildcards. In
C only lemmas are used and in D the original text (tokenized) is used. This
information is summarized in Table 3. The performances of these four
classifiers are similar. B outperforms the rest, which means that the proposed
strategy to keep the person information is not useful. Moreover the language
model size for B is smaller. A possible reason reason for the simpler model
outperforming the more complex is that there is not enough training data. As
expected, the model based on the original text performs worse and is the
biggest (the size includes the sum of the positive and negative models).

Figure 3:  Left: Receiver Operating Characteristic (ROC) curves for four language models (A,B,C and D) with different morphological changes, as described in Table 3. Right: The size of these models.  | A | B | C | D
---|---|---|---|---
Morphology removed | ✓ | ✓ | ✓ |
Person not included |  | ✓ | ✓ |
Unknown words replaced | ✓ | ✓ |  |
Named entities replaced | ✓ | ✓ |  |
Classifier success rate | $80.76\%$ | $81.97\%$ | $81.61\%$ | $79.85\%$
Area under the curve | $83.44\%$ | $86.51\%$ | $83.97\%$ | $81.00\%$
Table 3:  Characteristics of the language models of Figure 3.

Another question that has to be addressed is the maximum order of the
$n$-grams of the language model. In statistical machine translation orders
between 5 and 7 are common. However in machine translation the corpora used to
train the models are considerably larger than our 709741-words corpus of
opinions. Due to this there is no significant difference in the performance of
higher order models, and even bi-grams perform well (Figure 4-Left). The
reason for similar performance is that infrequent $n$-grams are pruned. The
actual difference is in the size of the models (Figure 4-Right). In our case
we select a maximal order 5, because the classification performance is
slightly higher. The benefit of a high order would be increased with bigger
corpora.

Figure 4:  Left: Receiver Operating Characteristic (ROC) curves for four
language models with different $n$-grams order. Right: size of the models for
different $n$-grams order. In all of them the same morphological changes are
used: only lemmas and no named entities.

Thus the size of the labeled corpus of opinions is of prime importance. It is
also the main limitation of most companies which need opinion classification
for their particular context, an so, the first bottleneck to take into account
in statistical sentiment analysis. In Figure 5-Left the ROC plots show the
quality of the classifiers when trained with smaller subsets of our original
corpus. In Figure 5-Right we show how the classification performance and the
area under the curve increase with increasing size of corpus. In these figures
the maximal amount of $100\%$ and the maximal amount of $140,000$
lines/paragraphs correspond to the $75\%$ of our corpus because a $25\%$ of it
is kept for performance evaluation.

Figure 5:  Receiver Operating Characteristic (ROC) curve of the Opinum
classifier for financial opinions.

Although in Figure 5-Right the performance exhibits a linear-like growth, this
only means that the training set is insufficient for this setup. Of course,
language models have a limit for capturing the positive or negative character
of a text. In Cui et al. (2006) the authors evaluate opinion classification
based on $n$-grams with a larger dataset consisting of $159,558$ positive and
$27,366$ negative opinions. Their results are slightly superior but the data
sets are not comparable. They do not present an evaluation for increasing size
of the corpus. The fact that their number of positive and negative opinions
are very different is another question to address. In our setup we have a
still differing but better balanced amount of both classes. We found no
improvement by removing the surplus, on the contrary, the performance slightly
decreased.

##  6 Conclusions and future work

Opinum is a sentiment analysis system designed for classifying customer
opinions in positive and negative. Its approach based on morphological
simplification, entity substitution and $n$-gram language models, makes it
easily adaptable to other classification targets different from
positive/negative. In this work we present experiments for Spanish in the
financial domain but Opinum could easily be trained for a different language
or domain. To this end an Apertium morphological analyser would be necessary
(30 languages are currently available) as well as a labeled data set of
opinions. Setting $n$ for the $n$-gram models depends on the size of the
corpus but it would usually range from 4 to 6, 5 in our case. There are other
parameters which have to be experimentally tuned and they are not related to
the positive or negative classification but to the subjective qualifier
very/somewhat/little and to the confidence measure.

The classification performance of Opinum in our financial-domain experiments
is 81,98% which would be difficult to improve because of the noise in the data
and the subjectivity of the labeling in positive and negative. The next steps
would be to study the possibility to classify in more than two classes by
using several language models. The use of an external neutral corpus should
also be considered in the future.

In this work we show that one of the most important factors to take into
account is the available number of labeled opinions. The size of the corpus
shows to have much more impact on the performance than the order of the
$n$-grams or even the morphological simplifications that we perform. Arguably,
morphological simplification would have a greater benefit on larger corpora,
but this has to be further analysed with larger data sets.

In practice the classification performance can be improved by filtering the
corpus from noise. We have kept all the noise and outliers in order to be fair
with the reality of the data for the present study. However, many wrong-
labeled opinions can be removed. In our data set there were some users
checking the “recommend” box and placing one or two stars, or not recommending
the product and giving four or five stars. Also, we have seen that too short
opinions perform insufficiently, and in too long opinions the language does
not reflect well the positive or negative sense. Thus these opinions should be
filtered in an application based on Opinum.

As a future work, an important question is to establish the limitations of
this approach for different domains. Is it equally successful for a wider
domain? For instance, trying to build the models from a mixed set of opinions
of the financial domain and the IT domain. Would it perform well with a
general domain?

Regarding applications, Opinum could be trained for a given domain without
expert knowledge. Its queries are very fast which makes it feasible for free
on-line services. An interesting application would be to exploit the named
entity recognition and associate positive/negative scores to the entities
based on their surrounding text. If several domains were available, then the
same entities would have different scores depending on the domain, which would
be a valuable analysis.

## References

  * Blair-Goldensohn et al. (2008) Blair-Goldensohn, S., Neylon, T., Hannan, K., Reis, G. A., Mcdonald, R., Reynar, J., 2008. Building a sentiment summarizer for local service reviews. In: In NLP in the Information Explosion Era, NLPIX2008.
  * Blitzer et al. (2007) Blitzer, J., Dredze, M., Pereira, F., 2007. Biographies, bollywood, boomboxes and blenders: Domain adaptation for sentiment classification. In: In ACL. pp. 187–205.
  * Cui et al. (2006) Cui, H., Mittal, V., Datar, M., 2006. Comparative experiments on sentiment classification for online product reviews. In: proceedings of the 21st national conference on Artificial intelligence - Volume 2. AAAI’06. AAAI Press, pp. 1265–1270.
  * Federico and Cettolo (2007) Federico, M., Cettolo, M., 2007. Efficient handling of n-gram language models for statistical machine translation. In: Proceedings of the Second Workshop on Statistical Machine Translation. StatMT ’07. Association for Computational Linguistics, Stroudsburg, PA, USA, pp. 88–95.
  * Heafield (2011) Heafield, K., 2011. Kenlm: faster and smaller language model queries. In: Proceedings of the Sixth Workshop on Statistical Machine Translation. WMT ’11. Association for Computational Linguistics, Stroudsburg, PA, USA, pp. 187–197.
  * Hu and Liu (2004) Hu, M., Liu, B., 2004. Mining and summarizing customer reviews. In: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. KDD ’04. ACM, New York, NY, USA, pp. 168–177.
  * Koehn et al. (2007) Koehn, P., Hoang, H., Birch, A., Callison-Burch, C., Federico, M., Bertoldi, N., Cowan, B., Shen, W., Moran, C., Zens, R., Dyer, C., Bojar, O., Constantin, A., Herbst, E., 2007. Moses: open source toolkit for statistical machine translation. In: Proceedings of the 45th Annual Meeting of the ACL on Interactive Poster and Demonstration Sessions. ACL ’07. Association for Computational Linguistics, Stroudsburg, PA, USA, pp. 177–180.
  * Mcdonald et al. (2007) Mcdonald, R., Hannan, K., Neylon, T., Wells, M., Reynar, J., 2007. Structured models for fine-to-coarse sentiment analysis. In: Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics.
  * Pang et al. (2002) Pang, B., Lee, L., Vaithyanathan, S., 2002. Thumbs up? sentiment classification using machine learning techniques. In: In proceedings of EMNLP. pp. 79–86.
  * Raaijmakers et al. (2008) Raaijmakers, S., Truong, K. P., Wilson, T., 2008. Multimodal subjectivity analysis of multiparty conversation. In: EMNLP. pp. 466–474.
  * Taboada et al. (2011) Taboada, M., Brooke, J., Tofiloski, M., Voll, K., Stede, M., 2011. Lexicon-based methods for sentiment analysis. Comput. Linguist. 37, 267–307.
  * Tyers et al. (2010) Tyers, F. M., Sánchez-Martínez, F., Ortiz-Rojas, S., Forcada, M. L., 2010. Free/open-source resources in the apertium platform for machine translation research and development. The Prague Bulletin of Mathematical Linguistics (93), 67––76, iSSN: 0032-6585.


#  Spectral conditions for the existence of specified paths and cycles in
graphs ††thanks: Supported by the NNSF of China (No.11101057), China
Postdoctoral Science Foundation (No.20110491443) and Zhejiang Provincial
Natural Science Foundation of China(LY12A01016).

Mingqing Zhaia , Huiqiu Linb , Shicai Gongc
aSchool of Mathematical Science, Chuzhou University, Anhui, Chuzhou, 239012,
China
bDepartment of Mathematics, East China University of Science and Technology,
Shanghai, 200237, China
cSchool of Science, Zhejiang A & F University, Zhejiang, Linan, 311300, China
Corresponding author. E-mail addresses<EMAIL_ADDRESS>(M.Zhai);
<EMAIL_ADDRESS>(H.Lin); scgong@zafu.edu.cn(S.Gong).

###### Abstract

Let $G$ be a graph with $n$ vertices and $\lambda_{n}(G)$ be the least
eigenvalue of its adjacency matrix of $G$. In this paper, we give sharp bounds
on the least eigenvalue of graphs without given pathes or cycles and determine
the extremal graphs. This result gives spectral conditions for the existence
of specified paths and cycles in graphs.

AMS Classification: 05C50; 05C38

Keywords: Path; Cycle; Spectral radius; Least eigenvalue; Adjacency matrix

##  1 Introduction

Let $G=(V,E)$ be the graph with vertex set $V$ and edge set $E$. Let $|G|$ and
$e(G)=|E(G)|$ be the order and the size of $G$, respectively. A graph $G$ is
said $H$-free, if $G$ does not contain a copy of $H$. Denote by $P_{t}$ and
$C_{t}$ the path and cycle of order $t$, respectively. Let $N^{d}(u)=\\{v|v\in
V(G),d_{G}(v,u)=d\\}$, where $V(G)$ is the vertex set of $G$ and $d_{G}(v,u)$
is the distance between $u$ and $v$. Particularly, denote $N(u)=N^{1}(u)$ and
$d(u)=|N(u)|$. For two disjoint vertex sets $V_{1}$ and $V_{2}$, let
$e(V_{1},V_{2})$ be the number of edges with one endpoint in $V_{1}$ and
another in $V_{2}$. Let $A(G)$ be the adjacency matrix of a graph $G$. The
largest modulus of an eigenvalue of $A(G)$ is called the spectral radius of
$G$ and denoted by $\rho(G)$. It is known that for a connected graph $G$,
there exists a positive unit eigenvector corresponding to $\rho(G)$, which is
called the Perron vector of $G$.

A central problem of extremal graph theory is as follows: for a given graph
$H$, what is the maximum number of edges of an $H$-free graph of order $n$? In
the past decades, much attention has been paid to the spectral version of
above question, that is, what is the maximum spectral radius of an $H$-free
graph of order $n$? It is known that if $H$ is a star $K_{1,r+1}$, then the
extremal graph is an $r$-regular graph (see [8]). In recent years, Fiedler and
Nikiforov [6] solved the question for $H\cong C_{n}$ or $H\cong P_{n}$.
Nikiforov solved the case $H\cong C_{2k+1}$ for large enough $n$ (see [9]) and
the case that $H$ is a complete graph $K_{r+1}$ or a complete bipartite graph
$K_{2,r+1}$ (see [10]). In [11], Nikiforov showed if $G$ is a $C_{4}$-free
graph with $n$ vertices, then $\rho^{2}(G)-\rho(G)-(n-1)\leq 0$ with equality
if and only if $G$ is the friendship graph (now $n$ is odd). Moreover, he
conjectured if $G$ is a $C_{4}$-free graph with even vertices, then
$\rho^{3}(G)-\rho^{2}(G)-(n-1)\rho(G)+1\leq 0$ with equality if and only if
$G$ is a star of order $n$ with $\frac{n}{2}-1$ disjoint additional edges.
Zhai and Wang [18] showed this conjecture is true. In [12], Nikiforov obtained
the extremal graph for $H\cong P_{2k+2}$ or $H\cong P_{2k+3}$ and gave a
conjecture on $H\cong C_{2k+2}$ (see [12], Conjecture 15.). This paper solves
these two questions in the class of bipartite graphs (see Theorems 2.1 and
2.2).

Let $\lambda_{n}(G)$ be the least eigenvalue of a graph $G$ of order $n$. It
is known that $\lambda_{n}(G)=-\rho(G)$ for a bipartite graph $G$ (see [4]).
Recently, researchers have begun to pay attention to the least eigenvalues of
graphs with a given value of some well-known integer graph invariant: for
instance: order and size [1, 2, 5, 13], unicyclic graphs with a given number
of pendant vertices [7], matching number and independence number [14], number
of cut vertices [15], connectivity, chromatic number [16], domination number
[17]. This paper also gives a spectral extremal characterization on the least
eigenvalue of graphs (see Theorems 1.3 and 1.4).

###### Lemma 1.1

Let $G=<X,Y>$ be a bipartite graph, where $|X|\geq k$, $|Y|\geq k-1$. If $G$
does not contain a copy of $P_{2k+1}$ with both endpoints in $X$, then

$e(G)\leq(k-1)|X|+k|Y|-k(k-1).$ $None$

Equality holds if and only if $G$ is isomorphic to a complete bipartite graph
$K_{|X|,|Y|}$, where $|X|=k$ or $|Y|=k-1$.

###### Lemma 1.2

Let $G$ be a $P_{2k+3}$-free bipartite graph. If $G$ does not contain a
connected component isomorphic to $K_{k+1,k+1}$, then for an arbitrary vertex
$u\in V(G)$,

$e(N(u),N^{2}(u))\leq(k-1)|N(u)|+k|N^{2}(u)|-k(k-1),$ $None$

and equality holds if and only if the subgraph induced by $N(u)\cup N^{2}(u)$
is isomorphic to one of the following:
(i) $K_{|N(u)|,|N^{2}(u)|}$, where $|N(u)|=k$ or $|N^{2}(u)|=k-1$;
(ii) a graph obtained from $K_{k,|N^{2}(u)|}$ and an additional vertex $v\in
N(u)$ by joining it with $k-1$ vertices of $N^{2}(u)$.

###### Theorem 1.3

Let $G$ be a $C_{t}$-free graph of order $n$.
(i) If $t$ is odd or $n<t$, then
$\lambda_{n}(G)\geq-\sqrt{\lfloor\frac{n}{2}\rfloor\lceil\frac{n}{2}\rceil}$,
and equality holds if and only if $G\cong
K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}$.
(ii) If $t=2k+2$ and $n\geq t$, then $\lambda_{n}(G)\geq-\sqrt{k(n-k)}$, and
equality holds if and only if $G\cong K_{k,n-k}$.

###### Theorem 1.4

Let $G$ be a $P_{t}$-free graph of order $n$.
(i) If $n<t$, then
$\lambda_{n}(G)\geq-\sqrt{\lfloor\frac{n}{2}\rfloor\lceil\frac{n}{2}\rceil}$.
Equality holds if and only if $G\cong
K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}$.
(ii) If $n\geq t$, then $\lambda_{n}(G)\geq-\sqrt{k(n-k)}$, where
$k=\lfloor\frac{t-2}{2}\rfloor$. Equality holds if and only if $G\cong
K_{k,n-k}$ or $G\cong K_{2,2}\cup K_{1}$ for $(n,t)=(5,5)$.

In the remaining part of this paper, we give the proofs of Lemmas 1.1 and 1.2,
and Theorems 1.3 and 1.4.

##  2 Proofs

Proof of Lemma 1.1. We use induction on $|Y|$. If $|Y|=k-1$, then

$e(G)\leq e(K_{|X|,k-1})=(k-1)|X|.$

So, (1) follows and the equality holds if and only if $G\cong K_{|X|,k-1}$.

Now we suppose that the inequality holds for $|Y|\leq M$, where $M\geq k$.

Case 1. There exists a vertex $u\in Y$ such that $d_{G}(u)\leq k-1$, then by
the hypothesis,

$e(G-u)\leq(k-1)|X|+k(|Y|-1)-k(k-1).$

Hence we have

$e(G)=e(G-u)+d_{G}(u)<(k-1)|X|+k|Y|-k(k-1).$

Case 2. For each vertex $u\in Y$, $d_{G}(u)\geq k$. We use induction on $|X|$.
If $|X|=k$, then

$e(G)\leq e(K_{k,|Y|})=k|Y|,$

so (1) follows and the equality holds if and only if $G\cong K_{k,|Y|}$.
Suppose that the inequality holds for $|X|\leq M$ where $M\geq k+1$.

Subcase 2.1. There exists a vertex $v\in X$, such that $d_{G}(v)\leq k-2$,
then by the hypothesis, we have

$e(G-v)\leq(k-1)(|X|-1)+k|Y|-k(k-1).$

Hence

$e(G)=e(G-u)+d_{G}(u)<(k-1)|X|+k|Y|-k(k-1).$

Subcase 2.2. For each vertex $v\in X$, $d_{G}(v)\geq k-1$. We may assume that
$G$ is connected. Otherwise, we use the induction hypothesis on each component
of $G$ and the inequality follows immediately. Now we suppose that $P$ is a
longest path in $G$ with two endpoints $w_{1},w_{2}$.

Subcase 2.2.1. Either $w_{1}$ or $w_{2}$ in $Y$, say $w_{1}\in Y$. Then
$|P\cap Y|\geq|P\cap X|$. Note that $G$ is $P_{2k+2}$-free, then $|P\cap
X|\leq k$. Since $d_{G}(w_{1})\geq k$, thus we have $|P\cap X|=k$ and
$N_{G}(w_{1})=P\cap X$. One can find now each vertex in $P\cap Y$ is an
endpoint of a path of the same length with $P$. Similarly, we have
$N_{G}(w)=P\cap X$ for any $w\in P\cap Y$. Then $X=P\cap X$ (otherwise we can
find a path with length longer than $|P|$ which is forbidden). Thus we have
$d_{G}(u)=k$ for each $u\in Y$ since $d_{G}(u)\geq k$ and $|X|=|P\cap X|=k$.
Therefore $G\cong K_{k,|Y|}$ and then the inequality in (1) is an equality.

Subcase 2.2.2. Both $w_{1}$ and $w_{2}$ are in $X$. Then $|P\cap X|=|P\cap
Y|+1$. Note that $G$ does not contain a copy of $P_{2k+1}$ with both endpoints
in $X$, then $|P\cap Y|\leq k-1$. Since $P$ is a longest path in $G$, thus
$N_{G}(w_{1})\subset P\cap Y$. Hence we have $N_{G}(w_{1})=P\cap Y$ and
$d_{G}(w_{1})=|P\cap Y|=k-1$ since $d_{G}(w_{1})\geq k-1$. Further, each
vertex $u\in X$ is an endpoint of a path of the same length with $P$. So we
have $d_{G}(u)=k-1$ for each vertex $u\in X$. Similarly, we have $Y=P\cap Y$.
Therefore, $G\cong K_{|X|,k-1}$ and then the inequality in (1) is an equality.

Thus we complete the proof. $\Box$

Proof of Lemma 1.2. Denote by $H$ the subgraph of $G$ induced by $N(u)\cup
N^{2}(u)$. By Lemma 1.1, if $H$ does not contain a copy of $P_{2k+1}$ with
both endpoints in $N(u)$, then Inequality (2) holds, and equality holds if and
only if $G\cong K_{|N(u)|,|N^{2}(u)|}$ with $|N(u)|=k$ or $|N^{2}(u)|=k-1$.
Now suppose that $H$ contains a path $P$ of order $2k+1$ with both endpoints
in $N(u)$.

Since $G$ is $P_{2k+3}$-free, $N(u)\backslash V(P)=\emptyset$ which implies
that $|N(u)|=k+1$ and $|N^{2}(u)|\geq k$. We distinguish the following two
cases.

Case 1. There is a vertex $v\in N(u)$ such that $d_{H}(v)\leq k-1$. Now,

$e(H-v)\leq
e(K_{k,|N^{2}(u)|})=k|N^{2}(u)|=(k-1)|N(u)|+k|N^{2}(u)|-(k+1)(k-1),$

and equality holds if and only if $H-v\cong K_{k,|N^{2}(u)|}$. Therefore,

$e(H)=e(H-v)+d_{H}(v)\leq(k-1)|N(u)|+k|N^{2}(u)|-k(k-1)$

If equality holds, then $d_{H}(v)=k-1$.

Case 2. For each vertex $v\in N(u)$, $d_{H}(v)\geq k$. Now let $w\in N(u)$ be
an endpoint of $P$. Note that $P$ is a longest path in $H$. Then $d_{H}(w)\geq
k$ and $N_{H}(w)\subseteq V(P)\cap N^{2}(u)$. However, $|V(P)\cap
N^{2}(u)|=k$. Hence $N_{H}(w)=V(P)\cap N^{2}(u)$. Further, we can find that
each vertex $x\in N(u)$ must be an endpoint of a path of order $2k+1$ in $H$.
Correspondingly, $N_{H}(x)=V(P)\cap N^{2}(u)$. This implies that $V(P)$
induces a copy of $K_{k+1,k}$. Since $G$ is $P_{2k+3}$-free,
$N^{2}(u)\backslash V(P)=\emptyset$. Thus $H\cong K_{k+1,k}$. Since $G$ does
not contain a connected component isomorphic to $K_{k+1,k+1}$,
$N^{3}(u)\neq\emptyset$. We then have a path of order $2k+3$ in $G$, a
contradiction.

This completes the proof. $\Box$

###### Theorem 2.1

Let $G$ be a $C_{t}$-free bipartite graph of order $n$.
(i) If $t$ is odd or $n<t$, then
$\rho(G)\leq\sqrt{\lfloor\frac{n}{2}\rfloor\lceil\frac{n}{2}\rceil}$. Equality
holds if and only if $G\cong
K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}$.
(ii) If $t=2k+2$ and $n\geq t$, then $\rho(G)\leq\sqrt{k(n-k)}$. Equality
holds if and only if $G\cong K_{k,n-k}$.

Proof. (i) Recall that $K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}$
has maximal spectral radius among all bipartite graphs of order $n$. If $t$ is
odd or $n<t$, then
$\rho(G)\leq\sqrt{\lfloor\frac{n}{2}\rfloor\lceil\frac{n}{2}\rceil}$ since $G$
is bipartite. Equality holds if and only if $G\cong
K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}$.

(ii) Let $G$ be a bipartite graph without $C_{2k+2}$ and

$B=(b_{ij})_{n\times n}=A(G)^{2}-k(n-k)I,$

where $I$ is the identity matrix of order $n$. Since $G$ is $C_{2k+2}$-free,
$G$ does not contain a copy of $P_{2k+1}$ with both endpoints in $N(u)$ for
any $u\in V(G)$. Let $b(u)$ be the sum of the $u$-th row of $B$. Note that
$(A(G)^{2})_{u}$ is the number of walks of length 2 which are started from
$u$. Then by Lemma 1.1, for any $u\in V(G)$,

$\displaystyle b(u)$ $\displaystyle=$
$\displaystyle|N(u)|+e(N(u),N^{2}(u))-k(n-k)$ $\displaystyle\leq$
$\displaystyle|N(u)|+(k-1)|N(u)|+k|N^{2}(u)|-k(k-1)-k(n-k)$ $\displaystyle=$
$\displaystyle k(|N(u)|+|N^{2}(u)|)-k(n-1)$ $\displaystyle\leq$ $\displaystyle
k(n-1)-k(n-1)$ $\displaystyle=$ $\displaystyle 0.$

If the equality holds, then by the second inequality, $N^{3}(u)=\emptyset$.
Further, by the first inequality and Lemma 1.1, $G-u\cong
K_{|N(u)|,|N^{2}(u)|}$ with $|N(u)|=k$ or $|N^{2}(u)|=k-1$. This implies that
$G\cong K_{k,n-k}.$

Let $X$ be an eigenvector of $G$ corresponding to $\rho(G)$ with
$\sum_{i=1}^{n}x_{i}=1$. Then

$\rho^{2}(G)-k(n-k)=\sum_{i=1}^{n}[\rho^{2}(G)-k(n-k)]x_{i}=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}b_{ij}x_{j}=\sum\limits_{u\in
V(G)}b(u)x_{u}\leq 0.$

Thus we have $\rho(G)\leq\sqrt{k(n-k)}$. If the equality holds, then $b(u)=0$
for any $u\in V(G)$. Thus $G\cong K_{k,n-k}$. On the contrary, if $G\cong
K_{k,n-k}$, then $\rho(G)=\sqrt{k(n-k)}.$ This completes the proof. $\Box$

###### Theorem 2.2

Let $G$ be a $P_{t}$-free bipartite graph of order $n$.
(i) If $n<t$, then
$\rho(G)\leq\sqrt{\lfloor\frac{n}{2}\rfloor\lceil\frac{n}{2}\rceil}$. Equality
holds if and only if $G\cong
K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}$.
(ii) If $n\geq t$, then $\rho(G)\leq\sqrt{k(n-k)}$, where
$k=\lfloor\frac{t-2}{2}\rfloor$. Equality holds if and only if $G\cong
K_{k,n-k}$ or $G\cong K_{2,2}\cup K_{1}$ for $n=t=5$.

Proof. Since $K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}$ has
maximal spectral radius among all bipartite graphs of order $n$, (i) holds
clearly. Next consider (ii).

If $t=2k+2$, that is, $G$ is $P_{2k+2}$-free, then $G$ is also
$C_{2k+2}$-free. Note that $K_{k,n-k}$ does not contain a copy of $P_{2k+2}$.
By (ii) of Theorem 2.1, the result holds.

If $t=2k+3$, then $n\geq 2k+3$. Note that

$\rho(K_{k,n-k})=\sqrt{k(n-k)}\geq\sqrt{k(k+3)}\geq(k+1)=\rho(K_{k+1,k+1}).$

Above inequalities become equalities if and only if $n=2k+3=5$, that is,
$n=t=5$. So we may assume that $G$ does not contain a connected component
isomorphic to $K_{k+1,k+1}$. Then by Lemma 1.2,

$e(N(u),N^{2}(u))\leq(k-1)|N(u)|+k|N^{2}(u)|-k(k-1)$

for any $u\in V(G)$.

Let $X$ be an eigenvector of $G$ corresponding to $\rho(G)$ with
$\sum_{i=1}^{n}x_{i}=1$ and

$B=(b_{ij})_{n\times n}=A^{2}(G)-k(n-k)I.$

Similar to the proof of Theorem 2.1, we have

$\rho^{2}(G)-k(n-k)=\sum_{i=1}^{n}[\rho^{2}(G)-k(n-k)]x_{i}=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}b_{ij}x_{j}=\sum\limits_{u\in
V(G)}b(u)x_{u}\leq 0.$

Hence, $\rho(G)\leq\sqrt{k(n-k)}$. If the equality holds, then $b(u)=0$ for
any $u\in V(G)$. This also implies that $N^{3}(u)=\emptyset$ and (2) becomes
an equality for any $u\in V(G)$. Note that if the case (ii) of Lemma 1.2
occurs, then $d_{G}(u)=k+1$ and $d_{G}(v)=k$. Thus either $G-u\cong
K_{k,|N^{2}(u)|}$ or $G-u\cong K_{|N(u)|,k-1}$ (otherwise, there will exist a
vertex $v\in V(G)$ such that $b(v)<0$). So $G\cong K_{k,n-k}$. we complete the
proof. $\Box$

The following lemma is very useful in characterizing the extremal graph with
minimal least eigenvalue.

######  Lemma 2.3 ([3])

If $G$ is a simple graph with $n$ vertices, then there exists a spanning
bipartite subgraph $H$ of $G$ such that $\lambda_{n}(G)\geq\lambda_{n}(H)$
with equality if and only if $G\cong H$.

Using Lemma 2.3 and Theorems 2.1 and 2.2, we immediately get Theorems 1.3 and
1.4.

Acknowledgment Thanks to Prof. Guanghui Xu who organized a workshop in
Zhejiang A & F University during Aug. 04-10.

## References

  * [1] F.K. Bell, D. Cvetković, P. Rowlinson, S.K. Simić, Graph for which the least eigenvalues is minimal, I, Linear Algebra and its Applications, 429 (2008) 234-241.
  * [2] F.K. Bell, D. Cvetković, P. Rowlinson, S.K. Simić, Graph for which the least eigenvalues is minimal, II, Linear Algebra and its Applications, 429 (2008) 2168-2179.
  * [3] D.S. Cao, Y. Hong, The distribution of eigenvalues of graphs, Linear Algebra and its Applications, 216 (1995) 211-224.
  * [4] D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs, third ed., Barth, Heidelberg, 1995.
  * [5] Y.Z. Fan, Y. Wang, Y.B. Gao, Minimizing the least eigenvalues of unicyclic graphs with application to spectral spread, Linear Algebra and its Applications, 429 (2-3) (2008) 577-588.
  * [6] M. Fiedler, V. Nikiforov, Spectral radius and Hamiltonicity of graphs, Linear Algebra and its Applications, 432 (2010) 2170-2173.
  * [7] R.F. Liu, M.Q. Zhai, J.L. Shu, The least eigenvalues of unicyclic graphs with $n$ vertices and $k$ pendant vertices, Linear Algebra and its Applications, 431 (5-7) (2009) 657-665.
  * [8] H. Minc, Nonnegative matrices, John Wiley and Sons, New York, 1988.
  * [9] V. Nikiforov, A spectral condition for odd cycles in graphs, Linear Algebra and its Applications, 428 (2008) 1492-1498.
  * [10] V. Nikiforov, Bounds on graph eigenvalues II, Linear Algebra and its Applications, 427 (2007) 183-189.
  * [11] V. Nikiforov, The maximum spectral radius of $C_{4}$-free graphs of given order and size, Linear Algebra and its Applications, 430 (2009) 2898-2905.
  * [12] V. Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra and its Applications, 432 (2010) 2243-2256.
  * [13] M. Petrović, B. Borovićanin, T. Aleksić, Bicyclic graphs for which the least eigenvalue is minimum, Linear Algebra and its Applications, 430 (4) (2009) 1328-1335.
  * [14] Y.Y. Tan, Y.Z. Fan, The vertex (edge) independence number, vertex (edge) cover number and the least eigenvalue of a graph, Linear Algebra and its Applications, 433 (4) (2010) 790-795.
  * [15] Y. Wang, Y.Z. Fan, The least eigenvalue of a graph with cut vertices, Linear Algebra and its Applications, 433 (1) (2010) 19-27.
  * [16] M.L. Ye, Y.Z. Fan, D. Liang, The least eigenvalue of graphs with given connectivity, Linear Algebra and its Applications, 430 (4) (2009) 1375-1379.
  * [17] B.X. Zhu, The least eigenvalue of a graph with a given domination number, Linear Algebra and its Applications, 437 (2012) 2713-2718.
  * [18] M.Q. Zhai, B. Wang, Proof of a conjecture on the spectral radius of $C_{4}$-free graphs, Linear Algebra and its Applications, 437 (2012) 1641-1647.