WCCI 2010 IEEE World Congress on Computational Intelligence uly, 18-23, 2010-CCIB, Barcelona, Spai CEC IEEE A Graph-Based Friend Recommendation System Using genetic algorithm Nitai B Silva, Ing-Ren Tsang, George D.C. Cavalcanti, and Ing-Jyh Tsang Abstract-A social network is composed by communities of used to develop novel applications such asa individuals or organizations that are connected by a common recommendation system. interest Online social networking sites like Twitter, Facebook With the increase of the e-commerce. recommendations and Orkut are among the most visited sites in the Internet. Presently, there is a great interest in trying to understand the systems have been of great interest. This is due to the complexities of this type of network from both theoretical and possibility of increase sell obtained from success applied point of view. The understanding of these social recommendation. Sites that offer different products such as network graphs is important to improve the current social books, clothes and movies, most often also provides network systems, and also to develop new applications. Here, recommendations based on previous brought products. The weproposeafriendrecommendationsystemforsocialnetworkNetflixprize(http://www.netflixprize.com)isanexampleof based on the topology of the network graphs. The topology of continuous interesting in this field[14]. The problem of on. or In more We developed an algorithm that analyses the sub-graph global context information, is growing in both commercial composed by a user and all the others connected people and academic research interest rately by three degree of separation. However, only users Here, we proposed a friend recommendation system that suggested as a friend. The algorithm uses the patterns defined suggests new links between user nodes within the network. separated by two degree of separation are candidates to be by their connections to find those users who have similar The central problem can be viewed as a procedure to propose relevant parameters for nodes relationship using the developed based on the characterization and analyses of the information from the social network topology and statistical network formed by the user's friends and friends-of-friends properties obtained by using classical metrics of complex (FOF) networks. Even though, topology based approaches fo have already been . INTRODUCTION other researchers [11],[12], [13, we proposed a different the last few years, social networks have been increasing clustering indexes and a novel user calibration procedure both size and services. Social networking services using Genetic Algorithm(GA) (SNSs) such as Facebook, MySpace, Twitter, Flickr, The rest of the paper is organized as follows: In Section 2, YouTube and Orkut are growing in popularity and we briefly describe the Oro-Aro social network used to mportance and to some extent they are also contributing to a analyze the proposed recommendation system In section 3, change in human social behavior. Some of these SNSs the recommendation mechanism is explained in details. The already provide a service to recommend friends, even though process is divided in two erin the method used is not disclosed, we believe that an FoF network measurements are also defined and three important approach is mostly used. The topology of this type of indexes are introduced. In Section 4, we describe the network has been measured and analyzed by different experiments using the proposed system in the Oro-Aro researches[1 ],[2],[3]. Some interesting structural properties comparisons of the obtained samples. Finally, the such as power-law, small-world and scale-free network concluding remarks are presented in Section 6. characteristics have been reported [1]. Also the topological patterns of activities and the structure and evolution of IL. THE ORO-ARO SOCIAL NETWORK online social networks have been studied 3.7 A social network is a structured community of individuals Knowledge of the structure and topology of these complex or organization composed of nodes that are connected networks combined with quantitative properties such as size, through one or more particular kind of interdependence,like density, average path length or cluster coefficient can b ralues. ideas p conflict, and trading [4],[5]. Analysis and measurements of by FAcEPe- Fundacao de amparo a ciencia e tecnologia do estado de social networks examines the social relations in terms of Nitai B Silva, Ing-Ren Tsang and George C. D Cavalcanti are with the individual users of the system, and connections correspo Federal University of Pernambuco (UFPE), Center of Informatics(CIn), to the relations between the users of the snss Av. Prof. Luis Freire. s/n. Cidade Universitaria. CEP In our experiments, we used the data obtained from the Ing-jyhTsangiswithAlcatel-lucent,Bell-iabs,Copernicuslan50.Oro-arosocialnetwork(http://www.oro-aro.com)thatwas 2018Antwerp,Belgium(e-mail:ing-jyhtsang@alcatel-lucent.com). 978-1-4244-8126-2/10/$26.00⊙2010IEEEAbstract—A social network is composed by communities of individuals or organizations that are connected by a common interest. Online social networking sites like Twitter, Facebook and Orkut are among the most visited sites in the Internet. Presently, there is a great interest in trying to understand the complexities of this type of network from both theoretical and applied point of view. The understanding of these social network graphs is important to improve the current social network systems, and also to develop new applications. Here, we propose a friend recommendation system for social network based on the topology of the network graphs. The topology of network that connects a user to his friends is examined and a local social network called Oro-Aro is used in the experiments. We developed an algorithm that analyses the sub-graph composed by a user and all the others connected people separately by three degree of separation. However, only users separated by two degree of separation are candidates to be suggested as a friend. The algorithm uses the patterns defined by their connections to find those users who have similar behavior as the root user. The recommendation mechanism was developed based on the characterization and analyses of the network formed by the user’s friends and friends-of-friends (FOF). I. INTRODUCTION N the last few years, social networks have been increasing in both size and services. Social networking services (SNSs) such as Facebook, MySpace, Twitter, Flickr, YouTube and Orkut are growing in popularity and importance and to some extent they are also contributing to a change in human social behavior. Some of these SNSs already provide a service to recommend friends, even though the method used is not disclosed, we believe that an FOF approach is mostly used. The topology of this type of network has been measured and analyzed by different researches [1], [2], [3]. Some interesting structural properties such as power-law, small-world and scale-free network characteristics have been reported [1]. Also the topological patterns of activities and the structure and evolution of online social networks have been studied [3], [7]. Knowledge of the structure and topology of these complex networks combined with quantitative properties such as size, density, average path length or cluster coefficient can be Manuscript received February 8, 2010. This work was supported in part by FACEPE – Fundação de Amparo à Ciência e Tecnologia do Estado de Pernambuco. Nitai B. Silva, Ing-Ren Tsang and George C. D. Cavalcanti are with the Federal University of Pernambuco (UFPE), Center of Informatics (CIn), Av. Prof. Luis Freire, s/n, Cidade Universitária, CEP 50740-540 (phone: +55 81 2126 8430; e-mail: {nbs,tir,gdcc}@ cin.ufpe.br). Ing-Jyh Tsang is with Alcatel-Lucent, Bell-Labs, Copernicuslaan 50, 2018 Antwerp, Belgium (e-mail: ing-jyh.tsang@alcatel-lucent.com). used to develop novel applications such as a recommendation system. With the increase of the e-commerce, recommendations systems have been of great interest. This is due to the possibility of increase sell obtained from success recommendation. Sites that offer different products such as books, clothes and movies, most often also provides recommendations based on previous brought products. The Netflix prize (http://www.netflixprize.com) is an example of continuous interesting in this field [14]. The problem of product, service, and friend recommendation, or in more global context information, is growing in both commercial and academic research interest. Here, we proposed a friend recommendation system that suggests new links between user nodes within the network. The central problem can be viewed as a procedure to propose relevant parameters for nodes relationship using the information from the social network topology and statistical properties obtained by using classical metrics of complex networks. Even though, topology based approaches for recommendation systems have already been suggested by other researchers [11], [12], [13], we proposed a different clustering indexes and a novel user calibration procedure using Genetic Algorithm (GA). The rest of the paper is organized as follows: In Section 2, we briefly describe the Oro-Aro social network used to analyze the proposed recommendation system. In section 3, the recommendation mechanism is explained in details. The process is divided in two phase filtering and ordering, some network measurements are also defined and three important indexes are introduced. In Section 4, we describe the experiments using the proposed system in the Oro-Aro social network. Also, we describe some estimates and comparisons of the obtained samples. Finally, the concluding remarks are presented in Section 6. II. THE ORO-ARO SOCIAL NETWORK A social network is a structured community of individuals or organization composed of nodes that are connected through one or more particular kind of interdependence, like values, ideas, interests, business, friendships, kinship, conflict, and trading [4], [5]. Analysis and measurements of social networks examines the social relations in terms of nodes and connections. Nodes in such network represent individual users of the system, and connections correspond to the relations between the users of the SNSs. In our experiments, we used the data obtained from the Oro-Aro social network (http://www.oro-aro.com) that was A Graph-Based Friend Recommendation System Using Genetic Algorithm Nitai B. Silva, Ing-Ren Tsang, George D.C. Cavalcanti, and Ing-Jyh Tsang I WCCI 2010 IEEE World Congress on Computational Intelligence July, 18-23, 2010 - CCIB, Barcelona, Spain CEC IEEE 978-1-4244-8126-2/10/$26.00 c 2010 IEEE 233