The Impact of Situation Clustering in Contextual-Bandit Algorithm for Context-Aware Recommender Systems

Most existing approaches in Context-Aware Recommender Systems (CRS) focus on recommending relevant items to users taking into account contextual information, such as time, location, or social aspects. However, few of them have considered the problem of user's content dynamicity. We introduce in this paper an algorithm that tackles the user's content dynamicity by modeling the CRS as a contextual bandit algorithm and by including a situation clustering algorithm to improve the precision of the CRS. Within a deliberately designed offline simulation framework, we conduct evaluations with real online event log data. The experimental results and detailed analysis reveal several important discoveries in context aware recommender system.

INTRODUCTION
A considerable amount of research has been done in recommending interesting content for mobile users. Earlier techniques in Context-Aware Recommender Systems (CRS) [3,6,13,5,23,24] are based solely on the computational behavior of the user to model his interests regarding his surrounding environment like location, time and near people (the user's situation). The main limitation of such approaches is that they do not take into account the dynamicity of the user's content.
Few works found in the literature [14,22] solve this problem by addressing it as a need for balancing exploration and exploitation studied in the "bandit algorithm" [21]. A bandit algorithm B exploits its past experience to select documents (arms) that appear more frequently. Besides, these seemingly optimal documents may in fact be suboptimal, because of the imprecision in B's knowledge. In order to avoid this undesired situation, B has to explore documents by choosing seemingly suboptimal documents so as to gather more information about them. Exploitation can decrease short-term user's satisfaction since some suboptimal documents may be chosen. However, obtaining information about the documents' average rewards (i.e., exploration) can refine B's estimate of the documents' rewards and in turn increases long-term user's satisfaction. Clearly, neither a purely exploring nor a purely exploiting algorithm works well, and a good tradeoff is needed.
The authors on [14,22] describe a smart way to balance exploration and exploitation in the field of recommender systems. However, none of them consider the user's situation during the recommendation.
In order to give CRS the capability to provide the mobile user's information matching his/her situation and adapted to the evolution of his/her content (good exr/exp tradeoff in the bandit algorithm), we propose an algorithm witch takes into account the user's situation clusters for defining the (exr/exp) tradeoff, and then selects suitable situations for either exploration or exploitation.
The rest of the paper is organized as follows. Section 2 reviews some related works. Section 3 presents the user's model of our CRS. Section 4 describes the algorithms involved in the proposed approach. The experimental evaluation is illustrated in Section 5. The last section concludes the paper and points out possible directions for future work.

RELATED WORKS
We review in the following recent relevant recommendation techniques that tackle the two issues mentioned above, namely: following the evolution of the user's contents using bandit algorithm and considering the user's situation on recommender system.

Bandit Algorithms Overview
The (exr/exp) tradeoff was firstly studied in reinforcement learning in 1980's, and later flourished in other fields of machine learning [17,20]. Very frequently used in reinforcement learning to study the (exr/exp) tradeoff, the multi-armed bandit problem was originally described by Robbins [21].
The ε-greedy is the one of the most used strategy to solve the bandit problem and was first described in [15]. The ε-greedy strategy choose a random document with epsilon-frequency (ε), and choose otherwise the document with the highest estimated mean, the estimation is based on the rewards observed thus far. ε must be in the open interval [0, 1] and its choice is left to the user.
Another variant of the ε-greedy strategy is what Cesa-Bianchi and Fisher [15] call the ε-decreasing strategy. In this strategy, the document with the highest estimated mean is always pulled except when a random document is pulled instead with an ε i frequency, where n is the index of the current round. The value of the decreasing ε i is given by ε i = {ε 0 / i} where ε 0 ∈ ]0,1]. Besides ε-decreasing, four other strategies are presented in [4]. Those strategies are not described here because the experiments done by [4] seem to show that, with carefully chosen parameters, ε-decreasing is always as good as the other strategies.
Compared to the standard multi-armed bandit problem with a fixed set of possible actions, in CRS, old documents may expire and new documents may frequently emerge. Therefore it may not be desirable to perform the exploration all at once at the beginning as in [9] or to decrease monotonically the effort on exploration as the decreasing strategy in [15].
Few research works are dedicated to study the contextual bandit problem on Recommender System, where they consider user's behavior as the context of the bandit problem.
In [10], authors extend the ε-greedy strategy by updating the exploration value ε dynamically. At each iteration, they run a sampling procedure to select a new ε from a finite set of candidates. The probabilities associated to the candidates are uniformly initialized and updated with the Exponentiated Gradient (EG) [11]. This updating rule increases the probability of a candidate ε if it leads to a user's click. Compared to both εbeginning and decreasing strategy, this technique improves the results.
In [14], authors model the recommendation as a contextual bandit problem. They propose an approach in which a learning algorithm selects sequentially documents to serve users based on contextual information about the users and the documents. To maximize the total number of user's clicks, this work proposes the LINUCB algorithm that is computationally efficient.
The authors in [4,9,14,15,22] describe a smart way to balance exploration and exploitation. However, none of them consider the user's situation during the recommendation.

Managing the User's Situation
Few research works are dedicated to manage the user's situation on recommendation. In [7,18] the authors propose a method which consists of building a dynamic user's profile based on time and user's experience. The user's preferences in the user's profile are weighted according to the situation (time, location) and the user's behavior. To model the evolution on the user's preferences according to his temporal situation in different periods, (like workday or vacations), the weighted association for the concepts in the user's profile is established for every new experience of the user. The user's activity combined with the user's profile are used together to filter and recommend relevant content.
Another work [13] describes a CRS operating on three dimensions of context that complement each other to get highly targeted. First, the CRS analyzes information such as clients' address books to estimate the level of social affinity among the users. Second, it combines social affinity with the spatiotemporal dimensions and the user's history in order to improve the quality of the recommendations.
In [3], the authors present a technique to perform user-based collaborative filtering. Each user's mobile device stores all explicit ratings made by its owner as well as ratings received from other users. Only users in spatiotemporal proximity are able to exchange ratings and they show how this provides a natural filtering based on social contexts.
Each work cited above tries to recommend interesting information to users on contextual situation; however they do not consider the evolution of the user's content.  [14,22] Context-Aware Algorithms [3,7,13,18] Clustering-ε-greedy Table 1: Recommendation algorithms comparison Table 1 compares the existing algorithms and the one we propose (Clustering-ε-greedy) w. r. t. two criteria, namely the evolution user's content and the consideration of the user's situation.
In our work we aim at taking advantage of the surveyed approaches and improve their weaknesses. As shown in Table 1, none of the mentioned works tackles both problems of the evolution user's content and user's situation consideration in the recommendation. This is precisely what we intend to do with our approach (Clustering-ε-greedy), exploiting the following new features:  Modeling the CRS as a contextual bandit algorithm by considering the user's situation when managing the (exr/exp)-tradeoff on recommendation.
 Using clustering algorithm we accelerate the context process acquisition and we improve the precision of the CRS.
The two features cited above are not considered in the surveyed approaches as far as we know.
In what follows, we define briefly the structure of the user's model and the methods for inferring the recommendation situations. Then, we explain how to manage the exploration/exploitation strategy, according to the current situation.

USER AND CONTEXT MODELS
The user's model is structured as a case base, which is composed of a set of situations with their corresponding user's preferences, denoted where S i is a user's situation (Section 3.2.1) and UP i its corresponding user's preferences (Section 3.1).

The User's Preferences
The user's preferences are contextual and might depend on many factors, like the location or the current task within an activity. Thus, they are associated to the user's situation and the user's activity. Preferences are deduced during the user's navigation activities. A navigation activity expresses the following sequence of events: (i) the user's logs in the system and navigates across documents to get the desired information; (ii) the user expresses his/her preferences about the visited documents. We assume that a visited document is relevant, and thus belongs to the user's preferences, if there are some observable user's behaviors through two types of preference: -The direct preference: the user expresses his/her interest in the document by inserting a rate, like for example putting starts ("*") at the top of the document.
-The indirect preference: it is the information that we extract from the user's system interaction, for example the number of clicks on the visited documents or the time spent on a document.
Let UP be the preferences submitted by a specific user in the system at a given situation. Each document in UP is represented as a single vector d=(c 1 ,...,c n ), where c i (i=1, .., n) is the value of a component characterizing the preferences of d. We consider the following components: the total number of clicks on d, the total time spent reading d, the number of times d was recommended, and the direct preference rate on d.

Context Model
A user's context C is a multi-ontology representation where each ontology corresponds to a context dimension C=(O Location , O Time , O Social ). Each dimension models and manages a context information type. We focus on these three dimensions since they cover all needed information. These ontologies are described in [1] and are not developed in this paper.

Situation Model
A situation is a projection on one or several user's context dimensions. In other words, we consider a situation as a triple s To build a more abstracted situation, we interpret the user's behavior from this low-level multimodal sensor data using ontologies reasoning means. For example, from S, we obtain the following situation: For simplification reasons, we adopt in the rest of the paper the following notation: The previous example situation became thus: Among the set of captured situations, some of them are characterized as high-level critical situations.

THE PROPOSED RECOMMENDATION ALGORITHM
The problem of recommending documents can be naturally modeled as a multi-armed bandit problem with context information. In our case we consider the user's situation as the context information of the multi-armed bandit. Following previous work [12], we call it a contextual bandit. Formally, our contextual-bandit algorithm proceeds in discrete trials t = 1…T. For each trial t, the algorithm performs the following tasks: Our goal is to design the bandit algorithm so that the expected total reward is maximized.
In the field of document recommendation, when a document is presented to the user and this one selects it by a click, a reward of 1 is incurred; otherwise, the reward is 0. With this definition of reward, the expected reward of a document is precisely its Click Through Rate (CTR). The CTR is the average number of clicks on a recommended document, computed dividing the total number of clicks on it by the number of times it was recommended. It is important to know here that no reward r t,d is observed for unchosen documents d ≠ d t previously displayed.

The ε-greedy Algorithm
The ε-greedy strategy is sketched in Algorithm 1. For a given user's situation, the algorithm recommends a predefined number of documents, specified by parameter N. In this algorithm, UC={d 1 ,…,d P } is the set of documents corresponding to the current user's preferences; D={d 1 ,….,d N } is the set of documents to recommend; getCTR (Alg. 1, line 6) is the function which estimates the CTR of a given document; Random (Alg. 1, lines 5 and 8) is the function returning a random element from a given set; q is a random value uniformly distributed over [0, 1] which defines the exploration/exploitation tradeoff; ε is the probability of recommending a random exploratory document.

Clustering-ε-greedy()
To adapt the ε-greedy algorithm to a context aware environment, we propose to compute the similarity between the present situation and each one in the situation base; if there is a situation that can be reused; the algorithm retrieves it, and then applies the ε-greedy algorithm. The proposed Clustering-εgreedy algorithm is described in Algorithm 6 and involves the following four methods:

RetrieveCase()
Given the current situation S t , the RetrieveCase() method determines the expected user's preferences by comparing S t with the situations in past cases in order to choose the most similar one S p . The method returns, then, the corresponding case (S p , UP p ).
6: Select UP p from UP In Eq.1, sim j is the similarity metric related to dimension j between two concepts x t and x c . This similarity depends on how closely x t and x c are related in the corresponding ontology (location, time or social). α j is the weight associated to dimension j, and it is set out by using the arithmetic mean as follows: and T the number of trials in the previous recommendation.
The similarity between two concepts of a dimension j in an ontological semantics depends on how closely they are related in the corresponding ontology (location, time or social). We use the same similarity measure as [25] defined by Eq. 4: In Eq. 2, LCS is the Least Common Subsumer of x j t and x j c , and depth is the number of nodes in the path from the node to the ontology root.

RecommendDocuments()
In order to insure a better precision of the recommender results, the recommendation takes place only if the following condition To improve the adaptation of the ε-greedy algorithm to HLCS situations, we propose to make the following verification: If the most similar S p ∈ HLCS, the system recommends documents with a greedy strategy and inserts the current situation S t on the HLCS class of situations; otherwise the system uses the ε-greedy() method described in Alg. 1. Alg. 3 summarizes the functional steps of the RecommendDocuments() method. If S p ∈ HLCS then 6.

Auto_improvement()
After recommending documents applying the Recommend-Documents method, two methods are used for improving the system:

UpdatePreferences()
Depending on the similarity between the current situation S t and its most similar situation S p (computed with RetrieveCase()), being 3 the number of dimensions in the context, two scenarios are possible: -sim(S t , S p ) ≠ 3: the current situation does not exist in the case base (Alg. 4, line 5); the InsertCase() method adds to the case base the new case composed of the current situation S t and the current user preferences UP t .
-sim(S t , S p )= 3: the situation exists in the case base (Alg. 4, line3); the UpdateCase() method updates the case having premise situation S p with the current user preferences UP t .

SituationClustering()
To accelerate the computing similarity between the current situation S t and the situations existing in the case base, we use one of the simplest and most efficient algorithms for clustering large datasets [10], the K-means algorithm, which is based on the analysis of variances. This algorithm clusters a group of situation vectors into a predefined number of clusters. It starts with random initial cluster centroids and keeps reassigning the situations in the dataset to cluster centroids based on the semantic similarity between the situations and the cluster centroid. The reassignment procedure will not stop until a fixed iteration number t max (Alg 5, line 6). We call this algorithm the Situa-tionClustering() and it is shown in Alg. 5.  S is the set of situations that belong to cluster cl i and tt is the parameter that activate the clustering algorithm if the iteration tt of Context-ε-greedy() gets the value ct; this parameter is discussed in Section 5.2.1.
The Algorithm 6 summarizes the functional steps of the four methods described above: Input: ε, N, PS, S t , UP, B, t max ,ct ,N

Finding the Optimal Exploration-Exploitation Trade-off
In order to set out the optimal trade-off value ε, we iteratively update it by the method Compute-ε() (Alg.7). First we assume that we have a finite number of candidate values for ε, denoted by Hε= (ε 1 ,..., ε T ).
Our goal is to select the optimal ε from Hε. To this end, we apply the ε-greedy algorithm for proposing an ε i , and then we use a set of weights w = (w 1 ,...,w T ) to keep track of the feedback of each ε i , w i is increased if we receive a number of clicks l i from the user when we use ε i . Receive a click feedback l i from the user 10. w i = w i+ l i ; 11. εε = εε ∪ ε i

Endfor
In Alg. 7. εε is the set of ε that have been previously selected , n is the number of iteration of the learning algorithm, i is the identifier of ε and is the probability of proposing the argmax i (w i ), this parameter starts at low value and iteratively increases until the end of the learning step.

EXPERIMENTAL EVALUATION
In order to evaluate empirically the performance of our approach, and in the absence of a standard evaluation framework, we propose an evaluation framework based on a diary set of study entries. The main objectives of the experimental evaluation are: (1) to find the optimal parameters of our algorithm and (2) to evaluate the performance of the proposed algorithm w. r. t. the ε variation and the dataset size. In the following, we describe our experimental datasets and then present and discuss the obtained results.

Evaluation Framework
We have conducted a diary study with the collaboration of the French software company Nomalys 1 . This company provides a history application, which records the time, the current location, the social and navigation information of its users during their application use. The diary study has taken 18 months and has generated 178369 diary situation entries.  Table 2: Diary situation entries Each diary situation entry represents the capture of contextual time, location and social information. For each entry, the captured data are replaced with more abstracted information using time, spatial and social ontologies. Table 3

Finding the Optimal Parameters
In order to set out the optimal parameters of the Clustering-εgreedy as the iteration of the clustering algorithm and the threshold similarity value, we use a manual classification as a baseline and compare it with the results obtained by our technique. So, we take a random sampling of 1783 situations which corresponds to 10% of the situations entries, we manually gather similar situations; then we compare the constructed groups with the results obtained by our algorithm, with different parameters of the situation clustering and the similarity methods. The results show that the precision has started to converge when t has the value 60 achieving a precision of 0.819. Consequently, we use the identified optimal iteration value (t max = 60) for testing our CRS.

Parameterizing the SituationClustering algorithm
In order to know how long our Clustering-ε-greedy can get optimal result without running the clustering method, we apply the SituationClustering at a different iteration of the Clusteringε-greedy with an interval between [0, 100]. Results in Figure 2 shows that the precision starts to decrease when Clustering-ε-greedy made a clustering after each 40 iterations ct=40 (alg. 5). Therefore, we run the clustering method (SituationClustering) with ct=40 and t max = 60.

Experimental Results
In our experiments, we have firstly collected the 3000 situations (HS) with an occurrence greater than 100 to be statistically meaningful, and the 10000 documents (HD) that have been shown on any of these situations.
The testing step consists of evaluating the existing algorithms (TestedAlgorithm in Alg.8) by giving to these last as an entry a situation S j t selected randomly from the sampling HS, where t is the identifier of the situation, j is the number of time that the situation S t has selected and j max is the number occurrence of S t in HS. The evaluation algorithm calculate and display the average CTR every 1000 iterations, The average CTR for a particular iteration is computed by the method getAVCTR (Alg. 8, line 7) and it is the ratio between the total number of clicks and the total number of displays. The number of documents (N) returned by the recommender system for each situation is 10 and we have run the simulation until the number of iterations (i) reaches 10000. The evaluation algorithm is described in Algorithm 8.

Results for ε Variation
In order to evaluate only the impact of considering the user's situation clustering in our bandit algorithm, we have compared the presented algorithm to a variant were we omitted the clustering part of the clustering-ε-greedy that we called ε-greedy. Each of the competing algorithms requires a single parameter ε. Figure 4 shows how the average CTR varies for each algorithm with the respective ε.  Figure 4 shows that, when the parameter ε is too small, there is an insufficient exploration; consequently the algorithms have failed to identify interesting documents, and have got a smaller number of clicks (average CTR).
Moreover, when the parameter is too large, the algorithms seem to over-explore and thus lose a lot of opportunities to increase the number of clicks.
We can conclude from the evaluation that considering the user's situation clustering is indeed helpful for Context-ε-greedy to find a better match between the user's interest and the evolution of his content (documents).

CONCLUSION
In this paper, we have studied the problem of exploitation and exploration in context-aware recommender systems and propose a new approach that balances adaptively exr/exp by considering the situation clustering.
We have presented an evaluation protocol based on real mobile navigation contexts obtained from a diary study conducted with collaboration with the Nomalys French company. We have evaluated our approach according to the proposed evaluation protocol and show that it is effective.
In order to evaluate the performance of the proposed algorithm, we compare it with other standard exr/exp strategies. The experimental results demonstrate the positif impact of the situation clustering in the contextual bandit algorithm. In the future, we plan to extend our situation with more context dimension, and we plan to evaluate our approach using an online framework.


TEXT SIGNAGE RECOGNITION IN ANDROID MOBILE DEVICES

This study presents a Text Signage Recognition (TSR ) model in Android mobile devices for Visually Impaired People (VIP). Independence navigation is a lways a challenge to VIP for indoor navigation in unfamiliar surroundings. Assistive Technology such as Android smart devices has great potential to ass ist VIPs in indoor navigation using built-in speech syn thesizer. In contrast to previous TSR research whic h was deployed in standalone personal computer system usi ng Otsu’s algorithm, we have developed an affordabl e Text Signage Recognition in Android Mobile Devices u ing Tesseract OCR engine. The proposed TSR model used the input images from the International Conference on Document Analysis and Recognition (ICDAR) 2003 dataset for system training and testin g. The TSR model was tested by four volunteers who were blind-folded. The system performance of the TS R model was assessed using different metrics (i.e., Precision, Recall, F-Score and Recognition Formulas ) to determine its accuracy. Experimental results s how that the proposed TSR model has achieved recognitio n rate satisfactorily.

INTRODUCTION
According to World Health Organization (WHO), around 285 million people around the world are suffering from Visual Impairment and Blindness (WHO, 2013). In general, visual impairment is defined as the reduction of the eyesight that cannot be corrected by standard glasses or contact lens and it reduces a person's ability to perform some daily tasks. It is always a great challenge for VIP to walk along streets in town without the company of a guide dog or caretaker. With the advancement of assistive technology, the VIPs from the Western countries could perform their daily tasks like grocery shopping or even take a bus to go to various places independently. Some alternative ways had been proposed (Coughlan and Shen, 2013;Zhang et al., 2013;Katz et al., 2012;Sarfraz and Rizvi, 2007;Al-Saleh et al., 2011) so that VIP can get around independently with the help of technologies. However, most of these systems are based on carrying heavy equipment or a computer system and there are limited choices of text signage recognition applications that run on smart phones. Based on statistics from Infographic, approximately 46.9% of smart phone users from a total of 1.08 billion users are running their mobile applications in Android platform (http://www.go-gulf.com/blog/smartphone). Indeed, it has been a paradigm shift to design, develop and implement mobile text recognition applications for indoor signage objects.
The VIPs are not able to see the texts on the indoor sign boards clearly. However, there are many electronic gadgets available on the market but they are either too expensive or difficult for VIPs to handle those devices. We were inspired to initiate this research after a site visit to the National Council of the Blind Malaysia (NCBM) in Kuala Lumpur. From the interview sessions, we have learned that the VIP desperately needs affordable electronic gadgets to assist in navigating around various places independently without the help of caretakers (Foong and Safwanah, 2011).

JCS
This is especially pertinent for VIP who works as professionals such as lawyer, accountant or computer network manager (Tocheh, 2006).
Unlike previous TSR research which was developed in standalone system using MATLAB Release 2012 (Foong and Safwanah, 2011;Hairuman and Foong, 2011),an attempt was made to develop a Text Signage Recognition (TSR) Model in Android mobile devices for better portability. Based on our previous research, Hairuman and Foong (2011) applied canny edge detection algorithm, Hough Transformation and Shearing Transformation to detect and correct skewed signage images. In this study, the main objective is to propose a light weight text signage recognition model for VIPs in Android mobile devices using Tesseract OCR engine.
However, there were many challenges in text signage recognition such as low quality input images, limited bandwidth, low memory capacity, poor resolution and inadequate lighting. Adapting OCR on mobile devices poses another challenge, i.e., mobile devices have much lower processing capabilities than standalone workstation or personal computer. This portrayed an obstacle in particular for the recognition of signage images in mobile devices. The problem was intensified by the use of mobile applications that required real-time or on-the-fly processing. Fortunately, mobile devices offer its advantages beyond portability and ubiquity. Since smart phones are getting more affordable and widely use, they are no longer just a communication device. Smart phones or Android mobile devices are used to capture text images from signage objects and translate them to voice for VIPs or foreign tourists whose native languages are not in English.
Hence, we focus on offline mode in the development of text signage recognition for the VIP in Malaysia. The text images were translated by Tesseract OCR engine. Random public signage was snapped. Texts were extracted from the captured image that will be translated to text characters. Eventually, the text will be recognized and read out the text. The authors had implemented the TSR system in Samsung Galaxy S2 device using Android version 2.3.
The remainder of the paper is organized as follows. In Section 2 is the literature review. Section 3 describes the proposed Text Signage Recognition model. Section 4 includes the experimental results. Section 5 discusses the experimental findings. Section 6 describes some of the challenges and limitations of text Signage recognition. Section 7 states the conclusion and future work.

RELATED WORK
Recent researches in OCR using Neural Network or pattern recognition in which texts in an image are translated into a format that computers can manipulate usingmathematical formula. There are numerous devices and system applications that are beneficial to the VIPs. One of the most common devices is the domestic helperrobot that can recognize scene texts in real-time (Ruiz et al., 2013). Case et al. (2011) had built a robot to read the texts from office signage and performed a semantic mapping between the office location and the name of the office occupant. Those devices are helpful to the VIPs but there exists several drawbacks. First of all, the devices are cumbersome to carry around. Secondly, the devices lack ergonomics features for the VIP to operate on the devices.
The rapid development in mobile technology and the increasing number of smart phones users have captivated the attention of mobile application developers. Quite a number of OCR related applications that run on smart phones had been developed. There are numerous text detection/recognition and translation applications (Hsueh, 2011;Lue et al., 2010) from the market but they are without speech synthesizer. Those applications can be used at anytime and anywhere because they can be installed on the smart phones and carried around. However, it is mandatory to have internet connectivity for smart phone users to run their mobile applications in back-end server. Undeniably, it will be costly to do roaming if free WIFI is unavailable.
A considerable amount of related work that incorporates speech synthesizing ability with text recognition could be found in Tian et al. (2010;; Yi andTian (2011;; Wang et al. (2013) and Arditi and Tian (2013). The central theme of these works revolves around independence navigation and way finding by exploiting the capabilities of camera-based computer vision. Tian et al. (2010; and Wang et al. (2013) described in detailed manner their way finding methods to access unfamiliar indoor environments such as different rooms and other building amenities. Similarly, Yi and Tian (2011; detailed out their proposed framework that could extract text regions from scene images with complex backgrounds and multiple text appearances. Taking a different perspective that is more to the end-users' viewpoint, Arditi and Tian (2013) reported on the user interface preferences in the design of a camera-based navigation and way finding. The research's finding confirmed on the need for devices that can guide the VIPs to architectural landmarks in their environment. Likewise, the finding indicated preferences towards device

JCS
interfaces that could give the VIPs control over the new surroundings learnt.
Recently Zhang et al. (2013) conducted a study on state-of-the-art algorithms on scene text classification and detection and claimed that his proposed algorithm significantly outperformed the existing algorithms for character identification. Chang (2011) came up with an intelligent text detection and Extraction technique using Canny Edge Detection algorithm in addition to using fast Connected Component algorithm to filter noise to obtain features and candidate text. Gonzalez and Bargasa (2013) applied geometric and gradient properties to design a text reading algorithm for natural images. Carlos et al. (2013) presented a method for perspective recovery of natural scene texts where the geometry of the characters was estimated to rectify homography for every line of text. Koo and Tian (2013) and Shi et al. (2013) extracted connected components in images usingMaximally Stable Extremal Region (MSER) algorithm to perform scene text detection and recognition. In addition, Liu and Smith (2013) invented a simple algorithm that used the density of special symbols to detect equation regions in printed document. They claimed that the performance of the Tesseract OCR engine had improved after the detector was enabled. Thus, we decided to deploy Tesseract OCR engine as a backend engine for this research because we discover thatTesseract OCR engine is open source (http://code.google.com/p/tesseract-ocr/) and it is rankedthe top three of the optical character recognition system at the Fifth Annual Test of OCR Accuracy (Rice et al., 1996).

PROPOSED TEXT SIGNAGERECOGNITION (TSR) MODEL
As mentioned earlier, the Tesseract OCR engine has been shortlisted for this research because it is reliable, open source and free of charge. The recognition process of the Tesseract OCR engine mainly consists of features detection, segmentation, features extraction and lastly character recognition steps (Smith, 2007).
To shorten the development time, the authors had adopted also the Open Source Computer Vision (OpenCV)'s libraries for image processingbecause it contains a list of real time computer vision library functions which is free for academic use http://opencv.willowgarage.com/wiki/Welcome/). Figure 1 showsthe proposed Text Signage Recognition (TSR) Model. In a nutshell, the TSR model recognizes text in signage image based on the following steps: • Image Acquisition • Image Pre-Processing • Character Recognition using Tesseract OCR Engine • Speech Synthesizing Process

Image Acquisition
The text image was captured using Samsung Galaxy S2 device and stored as standard jpeg format or the image was selected from secured digital card in Android smart phone. The image may contain some unwanted noises such as blur images, complex background objects, illuminating objects. Thus, pre-processing steps are required to smoothen or reduce these noises forbetter recognition rate.

Image Pre-processing
The image pre-processing eliminates unwanted noise in signage objects. It comprises of a series of operations like convert to grayscale, morphology transformation, thresholding, find the edges of the characters, copy those characters in new white background and finally convert the gray scale image to binary image. The entire steps of image preprocessing are illustrated in Fig. 2.
The original colored image in Fig. 3 is converted into gray scale image by using cvtColor() function with "COLOR_BGR2GRAY" color space conversion code. (http://opencv.willowgarage.com/wiki/Welcome/). The gray scale image carries intensity information.
The formula used for color space conversion to gray scale is as shown in Equation (1) where, R, G and B are the normalized input Red, Green and Blue pixel values. Morphological Transformations will be carried out next on the image as shown in Fig. 4. Morph_Open(http://opencv.willowgarage.com/wiki/Wel come/) is the morphological operation that has been used in this research project. The image was first eroded and then dilated as shown in the following codes: dst =dilate(erode (src,element), element) Thresholding operation that was performed to convert from gray scale to binary image based upon Otsu's algorithm (Otsu, 1979). The digital gray scale image was partitioned into multiple segments or sets of pixels. The selected pixels must fall within the limit of the thresholdvalue. Otherwise the pixels values that are either above or below the threshold value will be rejected. A mask was created by applying the drawContours()function from the OpenCV library (http://opencv.willowgarage.com/wiki/Welcome/). The mask would eliminate and darken all background objects in the image and allow only the characters on the signage image to be visible as depicted in Fig. 6.
The masked image was copiedandpastedontoanother image withwhitebackground as illustrated in Fig. 7.
The image is finally converted to binary image before proceed to the character recognition process.

Character Recognition
The processed binary image will be further processed and converted to text during the character recognition process (Smith, 2007) without any internet connection. The characters outlined in the binary image were analyzed into Blobs using Connected Component Analysis. The Blobs were organized into text lines and then further divided into words.

Speech Synthesizing Process
The words or texts were then fed into the speech synthesizer for the Text-To-Speech (TTS) translation. The TTS read out the words if recognized correctly.

JCS
Otherwise, it either read out all the characters in the word one after another or no output was produced.

RESULTS
For the TSR prototype, the authors adopted a new paradigm shift to design its mobile user interface as simple as possible. Every option is performed in a few clicks. Figure 8 shows the mobile user interface design that consists of two options, i.e., either to select image from phone gallery or from its camera in the homepage.

Experiment Setup and Implementation
A total of 60 different samples of signage images were selected from the ICDAR 2003 dataset (http://algoval.essex.ac.uk/icdar/RobustWord.html). Of all the random samples selected, 60% of the selected images were used for training while the remaining samples were used for testing. The aim of the experiment was to determine the recognition rate of the TSR model. We used two open sources libraries i.e., OpenCV (Bradski and Kaehler, 2008) and Tesseract OCR engine during the development of the TSR mobile application. We installed the proposed TSR model on Samsung Galaxy SII device for system training and testing.

Training and Testing
Prior to system performance testing, we had four volunteers/users (3 males and 1 female) between 20-22 years old to train the TSR mobile application. The users manually input those images into the proposed model for training purpose. Samples of training and testing data were displayed in Fig. 9 and 10 respectively. The results of training and testing were tabulated in Table 1.
The Recognition Rate (RR) of the proposed TSR model is calculated using Equation (2): Based on our observation, the recognition rate for trainingis 16.7% higher than that for testing dataset as illustrated in Table 1. The huge discrepancy between training and testing dataset was due to noises that were inherent in the selected testing images. The testing samples downloaded from the ICDAR2003 dataset contained complex background objects which constituted the noise.

User Evaluation on Proposed TSR Model
The TSR model was tested by the four volunteers/users to estimate its recognition rate. All users were blind-folded. 15 signage images were randomly selected in which some characters were slanted or skewed. Each signage image was captured using Samsung Galaxy SII device. If the signage was recognized correctly (T = True), a tick (√) was placed in the entry. Otherwise the signage was not recognized (F = False). Table 2 shows the user evaluation results for the ICDAR 2003 Robust Word Recognition dataset.

JCS
From the experimental results illustrated in Table 2, it appeared that the TSR model could not detect and recognize the text signage for "Alarm" by user 1 and user 4, "AGENTS" by user 2, "PEPPER" by user 3, "Videos" by user no. 4, "1946" by user 1 and user 3, "EST." by user 2 and "YOU" by user 2 and user 3. However, the TSR could recognize signage for "STAFF", "2002", "GAS", "TRAFFIC", "South", "E14", "FLATS" and "SERVICE". In general, most slanted or skewed text images could be detected and recognized by the Tesseract OCR engine.

Comparison of Performance Evaluation Using Precision, Recall and F-Score
In this subsection, we compared the proposed TSR model's system performance results with other alternative models in terms of Precision, Recall and F-

DISCUSSION
We observed that the TSR model had encountered some hiccups in text recognition process. Firstly, it was noticed that those signage images with white colored text failed to be recognized correctly. This was because when texts were extracted, masked, copied followed by pasted onto a new white background image, the white texts were blended into the new image that had white background. Secondly, it recognized the character 'O' incorrectly as 'Q' and vice versa. Thirdly, signage that had illuminating texture cannot be recognized at all. Fourthly, any incomplete and cropped character in the captured image would be recognized wrongly by the TSR model as well. On the other hands, the proposed TSR model could recognize well on text signage that had simple/plain background. In addition, sometimes the speech synthesizer failed to speak the word correctly. For example, it pronounced the word "YOU" as "Y", "O" and "U" by reading out the characters one by one. The signage recognition would deteriorate further if the image captured were either too dim or too bright since the users were blind-folded.
As there was no prior comparative study conducted on the ICDAR 2003 datasetusing the Recognition Rate formula in Equation (2), further testing on more ICDAR 2003 images were conducted using alternative metrics (i.e., Precision, Recall, F-Score).
The experimental results of the proposed TSR model were demonstrated in Table 3.  Table 3, Yao et al. (2013) demonstrated that their algorithm had achieved average F-Score of 0.63 by minimizing energy cost function for each region in its surrounding text. The proposed TSR model which used the Tesseract OCR engine had performed better than Ashida's method (Lucas et al., 2003) that gave an average F-Score of 0.50. But our TSR model produced average F-Score of 0.61 which was below Yao's method (Yao et al., 2013).

CHALLENGES AND LIMITATIONS
Text detection and recognition have posed many challenges to research community. Researchers have attempted to bridge the research gap by improving the text detection and recognition techniques. Yet, there exist plenty of rooms for improvement. The challenges still persist in scene text recognition such as cluttered or complex background, small font size, inappropriate font style, slanted/skewed images, embossed images and poor lighting are the main contributing factors of poor detection and recognition rates. However, the greatest challenge for the visually impaired or blind people in capturing scene text is that the captured image tends to be out of focus, missing or partial text appeared in the captured image, or even image that contains illuminating color. Undoubtedly, lack of contrasting colors between foreground and background objects would also be a stumbling block to better text detection and recognition.
In the contrary, with the advancement in mobile technology, the prices of mobile devices have become cheaper and affordable. But, all mobile devices still have little memory and limited processing capability to process indoor text images. The offline operating mode is helpful in avoiding heavy roaming costs while using the TSR mobile application abroad.

CONCLUSION
The proposed TSR model which was deployed with Tesseract OCR engine could successfully recognize the text images from the International Conference on Document Analysis and Recognition (ICDAR) 2003 dataset with satisfactory recognition rate. We attempt to build a Text Signage Recognition model in Android mobile devices for visually impaired people in Malaysia.
Our approach is simple and easy to implement. The proposed model does not require the internet connection during its operating mode because the Tesseract OCR engine was embedded in the Android mobile devices. However, the major drawback for implementing text signage recognition is that its recognition performance suffers when compared to state-of-the-art algorithms for text extraction and recognition. Yet, the proposed TSR Model is capable of translating texts to speech through the built-in speech synthesizer.
At this juncture, the TSR model could recognize and pronounce English words only. In future, we intend to enhance the TSR prototype by translating any English texts to different languages such as Malay or Mandarin languages.

ACKNOWLEDGEMENT
Special thanks and gratitude to the National Council of the Blind Malaysia (NCBM) and the Research and Innovation Office (RIO) of Universiti Teknologi PETRONAS for providing support in this research.


extfieldsofstudy:
Computer Science
Medicine

text:
An Efficient Immunization Strategy for Community Networks

An efficient algorithm that can properly identify the targets to immunize or quarantine for preventing an epidemic in a population without knowing the global structural information is of obvious importance. Typically, a population is characterized by its community structure and the heterogeneity in the weak ties among nodes bridging over communities. We propose and study an effective algorithm that searches for bridge hubs, which are bridge nodes with a larger number of weak ties, as immunizing targets based on the idea of referencing to an expanding friendship circle as a self-avoiding walk proceeds. Applying the algorithm to simulated networks and empirical networks constructed from social network data of five US universities, we show that the algorithm is more effective than other existing local algorithms for a given immunization coverage, with a reduced final epidemic ratio, lower peak prevalence and fewer nodes that need to be visited before identifying the target nodes. The effectiveness stems from the breaking up of community networks by successful searches on target nodes with more weak ties. The effectiveness remains robust even when errors exist in the structure of the networks.

Introduction
Epidemics could lead to a serious loss in life and have a huge impact on the economy, as we witnessed during the outbreaks of SARS (severe acute respiratory syndromes) in 2003 and H1N1 Influenza A virus in 2009 [1][2][3]. The problem of preventing an epidemic in time is of great importance and it has attracted much attention from researchers across different fields [4][5][6][7][8][9][10][11][12]. While immunization and quarantine are the two basic measures [13][14][15], finding an efficient way of identifying the targets to be immunized or quarantined so as to suppress an infection effectively remains a pressing issue [16].
The hubs, individuals with high centrality, in complex networks are commonly believed to be the most influential nodes as they could affect their many neighboring nodes [17]. Kitsak et al. pointed out that the nodes with a high k-shell are more influential spreaders in some real networks [18]. Undoubtedly, it is important to identify such influential nodes, but an effective method would require global information about the network structure. In these global strategies, the influential hubs can be identified by centrality measures, such as the degree centrality [19,20], eigenvector centrality [21], and betweenness centrality [22,23]. Such global strategies, however, become impractical for large-scale networks. Another type of method requires only local information. The acquaintance immunization strategy (henceforth labeled as ACQ) [24] in which random acquaintances of randomly chosen nodes are immunized is an example of local search algorithms. ACQ was shown to be an efficient algorithm for large-scale networks with broad-degree distributions [24]. Community structure at the mesoscale level is ubiquitous in a variety of real complex systems [25,26] such as Facebook [27,28] and Twitter [29], which plays an important role in the dynamics of epidemics [30][31][32][33][34][35]. In the presence of communities, the weak ties connecting a pair of nodes belonging to different communities, called the bridge nodes [36][37][38], provide the pathways for information and diseases to propagate from one community to another. These bridge nodes were found to be more important than the hubs in diffusing information through community networks [39][40][41]. Therefore, identifying the bridge nodes in community networks are crucial in preventing epidemic outbreaks [42][43][44]. Deterministic and stochastic algorithms have been designed to search for the bridge nodes [45]. Chen et al. [46] proposed an immunization strategy based on an equal graph partitioning algorithm to identify the minimum group that separates a network into several clusters of approximately equal size. The role of the minimum separator group is similar to that of the bridge nodes connecting different communities. The algorithm is effective in that only a small immunization ratio is needed, which is the fraction of immunized nodes. However, the algorithm requires the structural information of the whole network. Similar to other global strategies, it becomes impractical due to the high computing cost and, more fundamentally, the lack the complete information in large networks. Salathe and Jones [45] proposed the community bridge finder (CBF), which is a stochastic algorithm to search for the bridge nodes based only on local structural information, and found that the method is more efficient than immunization strategies targeting different kinds of hubs.
Community networks typically exhibit a heterogeneous distribution in the number of weak ties originating from a bridge node [36,47]. In the worldwide air traffic network, for example, bridge nodes can be divided into four classes: nonhub connector nodes, nonhub kinless nodes, connector hubs, and kinless hubs [48]. It was found that immunizing bridge hubs that connect a community to many other communities could protect a network efficiently against epidemics [49]. Identifying the bridge hubs with a larger number of weak ties, however, is quite challenging as the mesoscopic-scale community structure is difficult to resolve for large-scale networks [50]. It is against this backdrop that we propose an immunization strategy that identifies the bridge hubs by random walks in an expanding friendship circle. The strategy, which we call bright-hub detector (BHD) relies only on local structural information. We compare results obtained by BHD with ACQ and CBF strategies and find that it performs better in simulated networks and empirical community networks generated from real data. Simulation results also show that our strategy has the merit of being robust against noise.

Results
To illustrate the community structure in real-world networks and the necessity of an algorithm that focuses on identifying the bridge hubs, we have analyzed the heterogeneity of bridge nodes in the networks of students in five universities in the US using Facebook data. Details on constructing the networks from data are given in the Materials and Methods section. Figure 1 shows the cumulative probability density P(k w ) that a bridge node has a degree k w or higher in the students' Facebook networks of Caltech, Princeton, Georgetown, Oklahoma, and North Carolina. The distributions indicate that it is important to identify the bridge nodes with more weak ties, in addition to identifying only the bridge nodes as in CBF.
We present results of three different strategies (ACQ, CBF and BHD) on choosing immunizing nodes in simulated and empirical community networks within the susceptible-infected-recovered (SIR) epidemiological model. Briefly, simulated networks of different modularity Q are generated by randomly connecting communities, which are themselves random networks, following the algorithm in Ref. [45]. Empirical networks are constructed from Facebook data of students in each of five US universities, with a link defined by two students being online friends and belonging to the same dormitory or the same major in the same year of study. Table 1 lists the properties of these empirical networks. Details about network construction, the three strategies, and SIR dynamics are given in the Materials and Methods section. The ACQ, CBF and BHD strategies rely only on local structural information. In ACQ [24], a node is randomly picked and then a neighbor of the chosen node is randomly selected for immunization. The algorithm has a higher chance to immunize the hubs. In CBF [45], a step forward in a self-avoiding walk is checked for a bridge between communities by examining the existence of links or paths from the neighbors of the last node back to the nodes visited in the trail of the self-avoiding walk. The node before crossing the bridge is then identified as the bridge node and immunized. In addition, the supplementary rule of immunizing a node that has been visited twice by self-avoiding walks would pick up some hubs. Here, we implemented CBF as given in Ref. [45]. The bridge-hub detector (BHD) that we proposed in this paper extends the self-avoiding searching scheme to examining the overlap and the existence of links from all the neighbors of the last node back to the union of the friendship circles of all the nodes in the trail of the walk. A pair of nodes, a bridge node and a bridge hub, are searched for immunization via a self-avoiding walk (Readers are referred to the Materials and Methods section for more information). In the SIR model, the parameters b and m are the transmission rate and the recovery probability, respectively. The extent of an epidemic is characterized by the final epidemic ratio R, the fraction of the population ever infected at the end of the epidemic, and the peak prevalence I m , the highest density of infected nodes in the population at a time during the epidemic.
To compare the performances of ACQ and CBF with that of BHD, we have carried out the SIR dynamics on simulated networks with different modularity. For a given immunization coverage f , i.e., fraction of immunized nodes, the final epidemic ratio R is obtained for each of the three strategies. The differences R ACQ {R BHD and R CBF {R BHD would indicate the performance of ACQ and CBF relative to BHD. Figure 2 shows the differences for various combinations of the modularity Q and coverage f . The differences are positive over most of the Q-f space, with BHD leading to about 6:1% (2:8%) of fewer nodes being infected than ACQ (CBF). The results indicate that BHD is, in general, more effective in suppressing an epidemic. There are patches in the Q-f space that BHD is out-performed by ACQ and CBF. This is particularly apparent for networks with a strong community structure characterized by a high modularity. For example, both ACQ and CBF perform better in networks with Q[[0.95,0.97]. In these cases, an epidemic outbreak is mostly restricted in a local community and thus the better strategies are those that could For every network, the community structure is detected by the method proposed by Newman and Girvan [55]. Weak ties and bridge nodes are then identified. The number of weak ties emanating from each bridge node is recorded to give the cumulative distribution. Results are shown for students' networks for Caltech (red squares), Princeton (green circles), Georgetown (blue up triangles), Oklahoma (cyan down triangles) and North Carolina (magenta diamonds). doi:10.1371/journal.pone.0083489.g001 confine and suppress an epidemic to within the community that the outbreak starts. Immunizing the hubs with large degrees as in ACQ and CBF can prevent epidemic spreading within a community more efficiently. BHD spends some of the immunization coverage on removing nodes that belong to neighboring communities rather than the community of the outbreak itself and this becomes less effective in saving the nodes within the outbreak community from infection than ACQ and CBF. Figure 3 shows the results of R ACQ {R BHD and R CBF {R BHD obtained for the empirical networks. In most cases, the final epidemic ratio is smaller for BHD than ACQ and CBF. For example, R BHD is on average 8:5% (6:0%) smaller than R ACQ (R CBF ) for the Caltech network, 4:3% (2:3%) smaller for the Princeton network, and 3:2% (2:2%) smaller for the Georgetown University network. For the Oklahoma University network, R BHD is about 3:0% (1:4%) smaller than R ACQ (R CBF ) when the immunization coverage is not too small, e.g. f~20% (f~22%). Similarly, R BHD is about 2:9% (1:0%) smaller than R ACQ (R CBF ) at f~20% (f~26%) for the North Carolina University network. In the Oklahoma and North Carolina networks, BHD is out-performed by CBF when the immunization coverage is low. The ability of CBF to immunize the bridge nodes and some hubs makes it more effective in networks with a high assortativity and heterogeneity. As shown in Table 1, the degree assortativity r and heterogeneity H are &0:327 (&0:217) and &8:240 (&6:941) for the Oklahoma (North Carolina) University network. For an immunization coverage of f &20%, BHD performs better in all empirical networks than both ACQ and CBF, with a maximum in R ACQ {R BHD near this coverage. When the coverage is higher (e.g. f w20%), the differences in R for the three algorithms diminish, as the many immunized nodes would tend to be effective in breaking up a community and suppress an epidemic regardless of the algorithm. The results for the differences in peak prevalence are given in Figure S1 and the features are essentially the same as those in Figure 3.
Whether an algorithm is effective in preventing an epidemic is closely related to its effectiveness in breaking up the network after immunizing or removing a certain fraction of nodes [51]. Let G a (f ), with a denoting ACQ, CBF and BHD, be the size of the giant component of the resulting network using the algorithm a and an immunization coverage f , and G(0) be the size of the giant Structural properties including the network size (N), number of edges (E), the community number (M), modularity (Q) [55], degree assortativity (r) [56], degree heterogeneity (H = Sk 2 T/SkT 2 )), clustering coefficient(C), average shortest path length (SdT) and average degree (SkT) are tabulated for each of the five empirical networks. doi:10.1371/journal.pone.0083489.t001   network. It is a result of the removal of some bridge hubs (bridge nodes with more weak links to other communities), by BHD, which would result in a network that has a smaller mean degree. This is indeed the case, as shown in Figure S2. The geometry of the resulting network also affects the duration of an epidemic. In particular, resulting networks with smaller mean degree lead to a longer duration, as the disease can only spread by infecting one node after another. BHD is therefore expected to have a longer epidemic duration, despite a smaller final epidemic ratio and prevalence. Figure S3 shows that the epidemic duration is slightly longer for BHD, as compared with those with ACQ and CBF. The effectiveness of BHD is further illustrated in Figure 5, which compares the number of weak ties of the bridge hubs and bridge nodes identified for immunization using BHD with that of the bridge nodes identified by CBF. The results show that BHD indeed can identify the nodes with more weak links for removal. In addition, the bridge nodes identified by BHD carry more weak ties than those identified by CBF, further improving the effectiveness. In the Princeton University network, however, the large mean community size (see Table 1) makes it difficult for both BHD and CBF to search for the bridge nodes.
A more efficient algorithm is one that visits fewer nodes before identifying the targeted nodes for immunization. Let S CBF and S BHD be the numbers of nodes visited by the self-avoiding walks before getting at the targeted nodes. Figure 6 gives S CBF =S BHD for the five empirical networks. For small immunization coverage (f ƒ20%), S CBF =S BHD &1:5, indicating that BHD is a more efficient algorithm.
Another aspect of an effective algorithm is the robustness to errors or noise in network information. Such errors are common in social networks due to, for example, the inconsistency for two individuals to express their relationship [52]. Using an empirical network, we have tested the robustness of BHD by adding or removing a number of links from the network. SIR dynamics is then studied on the modified network without and with the BHD algorithm. The resulting final epidemic ratios are denoted by R 0 and R BHD , respectively. Figure 7 shows the results of R_BHD~(R 0 {R BHD )=R 0 for different numbers of links added or removed, with a constant immunization coverage of 5%. The results show that BHD performs well even when the networks are modified randomly. More results corresponding to other values of immunization coverage are shown in Figure S4.

Summary and Discussion
The heterogeneous distribution of weak ties in real-world community networks points to the importance of the bridge hubs in the control of transmission of information or diseases but these nodes are difficult to identify. We have proposed and studied the effectiveness of a bridge-hub detector strategy. It is a local strategy searching for bridge nodes and bridge hubs based on the idea of referencing to an expanding friendship circle as a self-avoiding walk proceeds. We applied BHD to simulated networks and empirical networks among students in five US universities constructed by using social network data. In general, BHD is more effective in preventing an epidemic when compared with Figure 5. Comparison of average number of weak ties among immunized bridge hubs identified by BHD, bridge nodes identified by BHD and bridge nodes identified by CBF. BHD identifies a pair of nodes for immunization via a self-avoiding walk algorithm. One node is a bridge hub and another a bridge node.
The average number of weak ties among these two types of immunized nodes [red squares (BHD hubs) and gray diamonds (BHD nodes)] are shown for different values of immunization coverage f , together with the results from immunized bridge nodes identified by CBF (blue circles). Results are obtained by averaging over 10 4 realizations for each value of f . For comparison, the results based on the method proposed by Newman and Girvan [55] are shown as the green dashed lines. doi:10.1371/journal.pone.0083489.g005 other local immunization strategies such as ACQ and CBF, for a practical range of immunization coverage. It gives a smaller final epidemic ratio and peak prevalence. Its effectiveness can be attributed to better identification of immunized nodes that carry more weak ties than those picked up by ACQ and CBF. BHD thus breaks up the community networks more effectively and suppresses an epidemic. Although BHD and CBF are both based on selfavoiding walks, BHD is more efficient in that it identifies the immunization nodes after visiting fewer nodes. The good performance of BHD remains robust even when errors exist in the structure of the underlying network.
In general, BHD is capable of identifying bridge nodes with more weak ties and it is particularly useful in dealing with community networks with a broad distribution in the number of weak ties among the bridge nodes. It can be readily generalized to other tasks. For example, mistakenly chosen nodes could be reduced by requiring that a node must have been identified twice or more times before it is immunized. The algorithm can also be applied to overlapping [50] and time-varying [53] community networks.

Materials and Methods
We have studied the effectiveness of our local immunization strategy in simulated and empirical community networks using the susceptible-infected-recovered (SIR) epidemiological model. Here, we give the details with respect to the following issues: communitynetwork construction, bridge-hub detector algorithm, and SIR dynamics.

Simulated and empirical community networks
The simulated community networks of different modularity Q are generated by the algorithm given in Ref. [45]. There are m independent random communities. In each community, n nodes are randomly connected so that the mean degree is Sk in T. These communities are then connected randomly by E out links. The simulated community network thus has a total of mn nodes and mnSk in TzE out undirected links. We used the same set of parameters as in Ref. [45], namely m~50, n~40, Sk in T~8, and E out~2 000. After generating the network, the modularity Q can be evaluated according to the definition given in Ref. [25]. The modularity Q can be varied by rewiring some intercommunity links into intra-community links, following the rewiring procedures given in Ref. [45]. While the modularity increases with rewiring, the degree heterogeneity remains nearly unchanged.
Empirical community networks are constructed using the collegiate social network data from Facebook (www.facebook. com) studied in Ref. [27]. The data of five universities in the US are studied (Available: https://code.google.com/p/ socialnetworksimulation/). They include data of students from the California Institute of Technology (Caltech), Princeton University, Georgetown University, University of Oklahoma, and University of North Carolina. The data provide information on the dormitory, majoring subject and year of class of the members. Based on the data, a community network is constructed [45] by linking up two members when (i) they are online friends of each other, and (ii) they belong to the same dormitory or the same major in the same year of study. The largest connected component of the network is then retained for carrying out our study. Basic statistical properties of the five empirical networks are given in Table 1. These networks exhibit the small-world character with a high clustering coefficient and a short average path length. The high modularity indicates a strong community feature.

Local Immunization Strategies and Bridge-Hub Detector
The present paper compares results based on our bridge-hub detector algorithm (BHD) with those obtained by other local strategies based on acquaintance immunization (ACQ) and the community bridge finder (CBF). Before discussing the BHD algorithm, we outline the ideas behind ACQ and CBF.
The ACQ algorithm immunizes randomly chosen acquaintances of randomly chosen nodes [24]. In ACQ, a node is picked randomly and then a neighbor of the chosen node is picked randomly for immunization. The procedure is then repeated until the desired immunization coverage is achieved. Therefore, a node that is a neighbor of many other nodes, i.e., a hub, will have a higher chance to be chosen for immunization. The algorithm does not require any information about the degree of the nodes. It is efficient for large networks with a broad degree distribution. A similar algorithm that requires a node to be chosen two times according to the ACQ random-pick processes (ACQ2) before it is immunized has also been studied [24]. Comparing with ACQ, ACQ2 has a higher probability of immunizing the hubs.
Bridge nodes are important for transmission through community networks, but ACQ does not aim at the bridge nodes. In contrast, CBF is designed to search for bridge nodes [45]. It is an algorithm based on self-avoiding walks. To identify a bridge and its associated bridge node for immunization, a self-avoiding walk is executed starting from a randomly chosen node v 0 . The following procedure is taken after every step when the walk has visited three or more nodes (see Figure 8). For a walk after t steps (t §2), the set of all nodes visited in the t steps so far is denoted by fv t 0 g for all t 0~0 ,1, . . . ,t. Thus, v t is the node that the walk currently locates after step t and v t{1 is the node visited at step t{1. The first check is to examine whether the node v t has a link or several links to the nodes in the set fv t 0 g other than the link between v t and v t{1 . If it is the case, the self-avoiding walk continues to step tz1. If not, then v t{1 is considered a possible target of a bridge node. To determine whether the node v t{1 is a bridge node, two nodes are randomly chosen among all the possible nodes that the walk could go in step tz1, i.e., two neighbors of the node v t are randomly chosen from all the neighbors (except the node v t{1 due to the selfavoiding restriction of the walk). In the case that there is only one neighbor to choose from, the only neighbor will be considered. If there exists a path from any of the two chosen nodes back to any node in the set fv t 0 g, then the node v t{1 will not be regarded as a bridge node and the walk moves on from v t to some node v tz1 . If there exists no path back to the set fv t 0 g from both of the chosen nodes, v t{1 is regarded as a bridge node that connects two communities and it will be immunized. A new self-avoiding walk will start again at another randomly chosen node and the procedure is repeated until the desired immunization ratio is achieved. The idea behind CBF is that a community is formed by a circle of close friends, and thus when the two randomly chosen neighbors of v t cannot be traced back to the community that v t{1 belongs to, the link between v t{1 and v t is likely to be a bridge between two communities and so the node v t{1 is a bridge node. In practice, two additional checks are implemented to shorten the computing time [45]. Firstly, the number of nodes registered in a running path is kept at the length of ten, using the latest ten nodes visited. Secondly, the number of visits by any random walk for each node is recorded. When the number k of visits equals a certain number (k~2 in Ref. [45]), the node is immunized. We have implemented CBF following the algorithm in Ref. [45], where it has been shown that, without prior knowledge of the community structure, CBF is more efficient than ACQ and other immunization strategies that target at the different kinds of hubs. In its design, CBF does not aim at identifying the bridge hubs. In real-world community networks such as those in Facebook [47], worldwide air traffic network [48], and the five collegiate community networks studied here, the heterogeneous distribution in the number of weak ties among bridge nodes indicates the importance of bridge hubs. Figure 9 shows an example of a bridge hub through a visualization of the students' network in Caltech. We propose a bridge-hub detector (BHD) for more effective immunization in community networks. It is a local algorithm based on an expanding friendship circle and it does not rely on prior knowledge of the community structure. As in CBF, the algorithm starts with a self-avoiding walk at a randomly chosen node. The following procedure is taken after every step when the walk has visited three or more sites (see Figure 8). Let v t be the node that the walker locates after step t and f t be the set of all neighbors of the node v t . For a walk up to t steps (t §2), the following steps are carried out between the set f t and the set F t{1 :f 0 |f 1 |f 2 | . . . |f t{1 . The set F t{1 is the union of all the friendship circles of all the nodes visited by the walker up to the step t{1 and it expands as the self-avoiding walk proceeds. Apparently, we have v t{1 [f t . If every other node in f t either already belongs to the set F t{1 or has at least a link to the nodes within F t{1 , v t will not be taken as the target of immunization and F t will be updated to F t~ft |F t{1 . The self-avoiding walk then moves on from v t . Otherwise, there must be at least a node in f t that is not a member in F t{1 and is not connected to the nodes in F t{1 . The node v t is then targeted for immunization. In addition, among the nodes in f t that do not belong to F t{1 and cannot be linked back to F t{1 , one node (call it v H ) is randomly chosen for immunization. A pair of nodes, v t and v H , are immunized and the self-avoiding walk stops. A new walk is initiated at another randomly chosen node again. The procedure is repeated until the desired immunization ratio is achieved. Similar to the idea in ACQ, the immunized node v H in every self-avoiding walk is likely to be a bridge hub in the presence of heterogeneous distribution of weak ties among the bridge nodes, while v t is a bridge node. The algorithm is illustrated schematically in Figure 8. Practically, we terminate a walk when it fails to identify immunization nodes after 20 steps. As in CBF, BHD is effective when the search for immunization nodes begins after t §2 steps. Figure S5 in Supporting Information gives results when the search begins after different numbers of steps. Through computational complexity analysis (see Text S1 in Supporting Information for more details), the algorithms ACQ, CBF and BHD take on the worst-case run times that go as O(fN), O(fN 3 ) and O(f SkTN 3 ), respectively. For the different algorithms working on systems with the same parameters (the same network size N and immunization ratio f etc.), ACQ is the fastest, followed by CBF and BHD is the slowest. On a sparse network with small SkT, BHD will have almost the same computational complexity as CBF.

Epidemic Dynamics
The susceptible-infected-recovered (SIR) epidemiological model [54] is used to test the performance of different immunization strategies on community networks. In the model, each node in the network represents an individual that can be in one of three states: susceptible (S), infected (I), or refractory/recovered (R); and each link represents a connection that could spread a disease. When an immunization strategy is executed, a percentage of nodes are first removed from the network by implementing ACQ, CBF or BHD. The remaining nodes are set to the susceptible state. To initiate an infection, a node is randomly chosen and turned into the I state. In a time step, a susceptible node will be infected with a probability Figure 8. Schematic illustration of CBF strategy and BHD strategy. The CBF strategy: (a) A self-avoiding walk starts at a randomly chosen node v 0 . (b)-(c) The walk visited fv 0 ,v 1 ,v 2 g after two steps. The node v 2 does not have any other links back to v 0 and v 1 other than the link that took the walk from v 1 to v 2 . The node v 1 is a potential candidate of a bridge node. Two neighbors of v 2 , namely v 3 and v F2 , are randomly picked and each is examined for connections to the visited set of nodes. As v 3 has links with v 0 and v 1 , the target node v 1 is dismissed as a bridge node and the walk continues. (d) The walk moves to v 3 after three steps. The node v 3 has links to previously visited nodes v 0 and v 1 , and thus the walk continues. (e) The walk moves to v 4 after four steps. The node v 4 does not have any other links back to previously visited nodes other than the link that took the walk from v 3 to v 4 . The node v 3 is a potential target of a bridge node. Two neighbors of v 4 are randomly chosen. (f) If v R2 and v H are chosen, these nodes do not connect back to the previously visited nodes and v 3 is identified as a bridge node and immunized. The BHD strategy: (a) A self-avoiding walk starts at a randomly chosen node v 0 . (b)-(c) The walk visited v 0 , v 1 and v 2 after two steps. The set F 2 is the union of all the neighboring nodes or friendship circles of v 0 , v 1 and v 2 , as shaded in (c). (d) The walk moves to v 3 after three steps. The friendship circle f 3 of node v 3 consists of v 0 , v 1 , v 2 , and v 4 . As all the nodes in f 3 either belong to F 2 or have a link to at least a node in F 2 , the node v 3 is not a potential target for immunization. (e) The union of friendship circles is updated to F 3~f3 |F 2 as shaded. The walk continues and reaches node v 4 after four steps. The friendship circle R2 and v H , among them v R2 and v H do not belong to F 3 and do not have a link to nodes in F 3 . The node v 4 is then identified as a bridge node for immunization. In addition, among those nodes in f 4 that cannot be linked back to F 3 , one node, e.g., v H , is randomly chosen and identified as a bridge hub for immunization. doi:10.1371/journal.pone.0083489.g008 1{e ({bÃi) , where i is the number of infected nodes among the connected neighbors of the node. Here, b is a parameter characterizing the transmission rate. Meanwhile, an infected node has a recovery probability m to turn into the R state. Once an individual is in the R state, there will be no further change. In the simulations, the parameters are taken to be b~0:08 and m~0:2 to ensure an outbreak and the state of every node is updated synchronously in every time step. The dynamics ends when all infected nodes have recovered. The resulting population contains nodes only in the S state and R state. We record the final epidemic ratio R corresponding to the density of R nodes at the end of the epidemic, the peak prevalence I m corresponding to the highest density of infected nodes in the network during the epidemic, and the duration of epidemic before the dynamics ends, and compare these quantities for ACQ, CBF and BHD.  Figure S4 Robustness of BHD in networks with noise as modeled by addition and removal of links for 20% immunization coverage. As in Figure 7, the quantity DR BHD~( R 0 {R BHD )=R 0 is shown as a function of the number of links randomly added to or removed from an empirical network. Results are shown for each of the five empirical networks as labeled. The immunization coverage is f~20%. The SIR Figure 9. Visualizing the community structure and a bridge hub in the Caltech network. The Caltech network can be divided into 13 communities based on the method of Newman and Girvan [55], as illustrated by the different colors. Also illustrated is a bridge hub H that carries the largest number of weak ties and connects with other bridge nodes labeled as n 1 to n 13 . The number on a weak tie shows the difference in the numbers of weak ties originated from the node H and the bridge node at the other end of the weak tie. doi:10.1371/journal.pone.0083489.g009 parameters are b~0:08 and m~0:2. Results are obtained by averaging over 10 4 realizations for each value of added and removed links. (EPS) Figure S5 Effects of starting the search for immunization nodes from different number of steps on the final epidemic ratio. Results in the main text and figures are obtained by starting the search for immunization nodes two steps after a self-avoiding walk began. Here, results for starting the search after 1, 2, 3, 4, 5 steps are shown for each of the five empirical networks.