الگوریتم های ژنتیک (GA) و توپولوژی شبکه (همبندی شبکه) برای پیشنهاد دوستان در شبکه های اجتماعی

ABSTRACT Friend recommendations in social networks using genetic algorithms and network topology

The emergence of social networks from the Internet sparked a major reform in information spread. From data to search and from search to social interaction, users around the world are now more deeply involved with the Internet as userMgenerated content undergoes perpetual growth and expansion. Through adoption of social networks, userMgenerated content is far more accessible than before. A powerful aspect of social networks is the customization of user experiences.

Recommendation systems constitute a large role in providM ing quality customized user experiences. The main challenge in developing relevant friend recommendations is due to the dynamic nature of humans’ perception of friendship, which constitutes a cause for heterogeneity in social networks [1], [2]. It is natural and frequent for humans to change their perception of friendship [3]. Further, this perception varies from person to person in which a social network can undergo frequent and abrupt change over time even without the introM duction of new nodes [4].

In this paper, our goal is to study human interaction within social networks in order to gain insights into the preferences an individual considers when forming relationships so we can provide better quality, i.e., more relevant, friend recommendaM tions.

NetworkMbased approaches generally perform well in proM viding quality recommendations. Prior work in both industrial and academic sectors emphasize the use of the friendsMofM friends method. The intuition is derived from the idea that it is more probable a person will know a friend of their friend rather than a random person [5]. This approach implies a person is more likely to pursue a relationship based a common association. However, this does not provide any insights into human cognitive components, which is a multiMdimensional belief system that may change over time [6].

The use of genetic algorithms has been used to suppleM ment networkMbased approaches. Prior research has suggested genetic algorithms to be used to optimize a set of indices derived from complex network theory [7], [8]. This approach still relies purely on the underlying structural properties of social networks. Since participants within social networks are humans, it would be of significant interest to approach the recommendation problem by supplementing network theory with cognitive theory.

In this paper, we examine 1,200 Facebook users and generM ate individually customized quality sets of friend recommenM dations by applying a twoMstep filtering process using friendsM ofMfriends, degree centrality and a ParetoMoptimal genetic algoM rithm that optimizes relationship preferences. We aim to filter out likely irrelevant individuals using complex network theory before applying our ParetoMoptimal genetic algorithm. In our genetic algorithm, we aim to identify a set of social features that defines an individual’s perception of friendship, which in turn will filter out additional users. Finally, we rank a set of quality, relevant potential friends based on point valuations derived from the individual’s set of preferred features.

The results of this paper demonstrate that our combinational approach outperforms purely social and purely networkMbased approaches and provides strong support for future exploration of this method in developing better recommendation systems and user experiences within social networks. We tested our results by randomly removing 10 friends from an individual’s network in which a purely social, purely networkMbased, and the combined approach attempted to produce a recommendaM tion list containing as many of the previously removed friends as possible.

The rate of return was used to compare the performances of each algorithm. The purely social approach yielded a 6.83% return rate, with 0 to 2 of the removed users being recommended; the networkMbased approach yielded a 22.38% return rate, with 1 to 4 users being recommended; and finally the combined approach yielded a 31.78% return rate, with 1 to 6 users being recommended.

The remainder of this paper is organized as follows: In Section II, we describe prior approaches to developing recC ommendation systems. In Section III, we present complex netC work fundamentals used in the initial filtering step. Section IV presents our social genome representation and Section V describes the final filtering step and characterization of an individual’s preferred social features. We present our results in Section VI along with a discussion and conclude with a summary and future work in Section VII.