Trustworthy Website Detection Based On Social Hyperlink Network Analysis

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TNSE.2018.2866066, IEEETransactions on Network Science and EngineeringTRANSACTIONS ON NETWORK SCIENCE AND ENGINEERINGwith will be significantly reduced. Unfortunately, existingtrust-ranking based algorithms do not accurately model thetrustworthiness of web pages, and thus often mistakenlyidentify spams as trustworthy websites. To improve theperformance of trustworthy website detection, we approachthis problem by studying the trust relations among websites,leveraging social network analysis techniques.1.2Proposed SolutionTrust has been intensively studied in online social networks [19], [20], and the knowledge obtained from this fieldcan be applied to analyze the hyperlink network, consistedof websites, to understand website trustworthiness. Considering a website as an individual user, and the hyperlinksconnecting websites as the social relations among them, wecan model the network of websites as a social hyperlinknetwork.According to the three-valued subjective logic model(3VSL) [21], the trust relation between two websites canbe modeled as a trust opinion b, d, n . Based on theopinion operations defined in 3VSL, the trustworthinessof every website can be computed using the OpinionWalkalgorithm [22]. The algorithm starts from a seed node andsearches the network, in a breadth first search manner, tocompute the trustworthiness of all other nodes, from theseed node’s perspective. If multiple seed nodes are chosen,the algorithm will compute several different trust opinionsof the same node. These opinions will then be combined toobtain the trustworthiness of the node. As such, the websiteswith higher trust values can be ranked on top of the listprovided to users.To apply the OpinionWalk algorithm in trustworthywebsite detection, however, we need to address two challenges. First, the 3VSL models trust as an opinion vectorcontaining three values b (belief), d (distrust), and n (uncertainty). It unfortunately does not specify how the threevalues of an opinion are obtained. To initialize the trustopinion between two linked websites, we need to understand which factors affect the trustworthiness of a website.From previous studies, we find trustworthy websites rarelypoint to spam websites and the websites linking to spamsare likely to be spams [18] [23]. Therefore, by checking howmany trustworthy (or spam) websites a website links to,we can possibly determine the website’s trustworthiness,i.e., the values of b, d and n in the corresponding trustopinion. The second challenge lies in the large executiontime of the algorithm. As OpinionWalk searches a networklevel by level, the trustworthiness of all nodes will beupdated in each searching/iteration, which yields frequenttrust computation and updates that are often not necessary.To address this challenge, we design a mechanism to recordwhich websites’ trustworthiness need to be updated andonly change them when the algorithm “walks” through thenetwork. As a result, we are able to detect more trustworthywebsites within a relatively shorter period of time, compared to the state-of-art solutions [5], [18], [22].1.3ContributionsIn this paper, we discuss how to identify more trustworthywebsites by proposing the enhanced OpinionWalk (EOW)2algorithm. The key contributions of this paper are as follows.For the first time, the hyperlinks between websites areviewed as the “social” connections between websites. Leveraging the trust model designed for social networks, thetrustworthiness of websites can be quantified. Due to theaccuracy of 3VSL in modelling trustworthiness, individualwebsite’s trustworthiness can be precisely calculated, usingthe proposed EOW algorithm. Based on the previous research results, the trustworthiness of a website are mainlydetermined by the numbers of trustworthy and spam websites it links to. As only labeled websites’ trustworthiness areknown, we treat all other websites as uncertain/undecided.Therefore, by counting the numbers of trustworthy, spam,and uncertain websites a website points to, the website’strustworthiness opinion can be formed. We enhance theOpinionWalk algorithm by identifying which opinions needto be updated while the algorithm searching within a socialhyperlink network. Specifically, a Boolean vector is usedto keep track of the websites that are connected from thecurrent websites whose trustworthiness values are just updated. When the EOW algorithm searches the next levelin the network, only these websites’ trustworthiness arechanged accordingly. The proposed EOW algorithm is validated by experiments using the WEBSPAM-UK2006 datasetthat contains both trustworthy and spam websites crawledwithin the .uk domain. Experimental results indicate thatthe EOW algorithm identifies 16.5%, 12.65%, 8.77%, 5.35%more trustworthy websites, in the top 1000, 2000, 3000 and4000 websites, respectively, compared to TrustRank (thestart-of-art solution), when the number of trustworthy seedsis 200. In addition, EOW saves (on average) about 27.1%execution time, compared to the OpinoinWalk algorithm, incomputing the trustworthiness of all websites.The rest of this paper is organized as follows. In Section 2, we introduce the proposed EOW algorithm, followedby an example illustrating how it works. In Section 3, wedescribe how EOW algorithm performs, regarding to detecting trustworthy websites from a real-world dataset. Then,we summarize the related work of trustworthy websitedetection in Section 4. Finally, we conclude our work andpoint out future research directions in Section 5.2 D ETECTING T RUSTWORTHY W EBSITES USINGE NHANCED O PINION WALK A LGORITHMConsidering websites as users, a hyperlink network canbe modeled as a ”social network” that reflects the “socialconnections” among different websites. The connection between two linked websites can be assigned a weight toindicate the trustworthiness between them, which resultsin a weighted trust social network. Within the network,we can leverage trust propagation and trust combinationto compute the trustworthiness of individual websites. Assuch, trustworthy websites can be identified from all websites available.OpinionWalk was designed to solve the massive trustassessment problem in social networks [22], however, a fewchallenges need to be addressed before it can be appliedto trustworthy website detection. The first challenge is todesign a mechanism to assign weights on connections/links2327-4697 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TNSE.2018.2866066, IEEETransactions on Network Science and EngineeringTRANSACTIONS ON NETWORK SCIENCE AND ENGINEERINGso that the trustworthiness between websites can be reflected by the weights. The second challenge is to enhancethe OpinionWalk algorithm to make it more efficient as thecurrent OpinionWalk algorithm is very slow. We propose theenhanced OpinionWalk (EOW) algorithm that starts froma trustworthy node and searches the hyperlink network todetect more trustworthy websites.2.1Social Hyperlink Network ModelThe hyperlink graph of websites can be modeled as adirected graph G (V, E, W ), where vertex i V denotesa website, edge e(i, j) E represents the hyperlink fromwebsites i to j . We call website j as i’s adjacent node, andweight w(i, j) W of the edge e(i, j) indicates how i trustsj . We further define the indegree of a website as the numberof websites pointing to it. The outdegree of a website isdefined as the number of websites that it points to. Theweight on each edge in graph G is usually modeled as a realnumber [19], however, we find it cannot accurately reflectthe trust between two nodes [21]. To conduct precise trustcomputation, OpinionWalk algorithm defines the trust as anopinion vector that contains three numbers reflecting howlikely a user is trustful, not trustful and uncertain, respectively. We adopt this definition and propose a mechanismto assign the three values of an opinion in the trustworthywebsite detection problem.2.2Edge Weight AssignmentBy analyzing the structure of existing hyperlink graphs, wefind that a trustworthy site rarely links to a spam site [18].Besides, a website pointing to many spam sites is very likelyto be a spam site [23]. By looking at how many trustworthywebsites that a website points to, and how trustworthy thesewebsites are, we are able to determine the trustworthinessof the website. In other words, the quality and quantityof pointed websites should be considered in modeling thetrustworthiness of a website.i}tjtrustworthyspamuncertainFig. 1: Illustration of weight assignment in a hyperlinkstructure graph.For trustworthy website detection, there are usually agroup of websites that are labeled as either normal or spamby humans. This group of websites is commonly referredto as a labeled set. We further divide the labeled set intotwo groups: seed set and testing set. While the former isused to initialize trust relations between websites, the latteris used for evaluation purpose. As shown in Fig. 1, we nowfocus on the nodes that website j points to. These nodescould be either trustworthy, not trustworthy, or uncertain,depending on the nature of the corresponding websites. Assuch, we consider a labeled normal website as a trustworthyone, a spam website as a untrustworthy one. For those thatare not analyzed by humans, or not being labeled, we callthem undecided or uncertain websites.3We use gj , sj and uj to denote the number of labeledgood/normal websites, labeled spam websites, and undecided websites that j points to. Let bj , dj , nj denote theprobabilities that website j is trustworthy, not trustworthy,and uncertain, respectively. According to the three-valuedsubjective logic [21] that is used to model trust in OpinionWalk [22], these probabilities can be computed as follows. gj b g s uj 3 jjj sj dj gj sj uj 3.(1)uj n j g s u 3jjj 3 ej g s u 3jjjIn the above equations, ej denotes the prior uncertaintyexisting in website j . As we can see, if website j pointsto no other website, the values of bj , dj and nj are zerosand ej 1, indicating the trustworthiness of website j isunknown or fully uncertain. In this case, we assume websitej points to 3 virtual websites, a normal one, a spam one, andan uncertain one. This is why ej is called as the prior uncertainty of website j . The assumption is reasonable becauseEq. 1 considers both prior (ej ) and posterior uncertainties(nj ) and still works even website j does not point to anyother website. More details about the difference betweenprior and posterior uncertainties can be found in [21].Based on the above analysis, we model the trustworthiness between two websites i and j as an opinion vectorωij (bij , dij , nij , eij ) (bj , dj , nj , ej ). ωij indicates howtrustworthy website j is, from website i’s perspective. Asshown in Fig. 1, if there is another website t also pointing toj , we have ωtj ωij (bj , dj , nj , ej ). Note that ωij ωtj ,which is different from OpinionWalk that assumes differentusers have different opinions on the same user.If there is no hyperlink from i to j , i.e., e(i, j) / E,then we define i has an uncertain opinion O on j as O (0, 0, 0, 1) that indicates a website is totally uncertainabout whether another website is trustworthy. For ωii , a certain opinion I is defined as I (1, 0, 0, 0) that indicates awebsite absolutely trusts itself.2.3Opinion Matrix InitializationGiven a hyperlink graph G (V, E, W ) containing n nodesand a subset S V with labeled nodes, we can obtain theopinion matrix M , as it is defined in [22]. In the matrix,ωij (bj , dj , nj , ej ) is calculated from Eq. 1, if e(i, j) E ;otherwise, ωij O except for ωii I. Iω12 . ω1n ω21I··· ··· M · · · · · · · · · · · · .ωn1 · · · · · ·IThe opinion matrix records all the trust relations amongwebsites that are connected to each other. This matrix willthen be used to compute trustworthiness of all websites,which will be introduced in later sections.Algorithm 1 shows how to initialize the opinion matrix,based on a directed graph G and a labeled seed set S .Please note that S is composed of websites that are selectedfrom the labeled set with seed selection method described in2327-4697 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TNSE.2018.2866066, IEEETransactions on Network Science and EngineeringTRANSACTIONS ON NETWORK SCIENCE AND ENGINEERINGsection 3.1.1. Lines 1-9 initialize the opinion matrix M withI or O. Lines 10-28 update M [i][j] based on the numberof normal, spam and unlabelled websites that j points to.Finally, line 29 returns the opinion matrix M .Algorithm 1 GetOpinionMatrix(G, S )Require: Directed graph G, labeled seed set S .Ensure: Opinion matrix M .1: for all node i do2:for all node j do3:if i j then4:M [i][j] I5:else6:M [i][j] O7:end if8:end for9: end for10: for all node i do11:for all nodes j s.t. e(i, j) E do12:gj 0, sj 0, uj 0;13:for all nodes p s.t. e(j, p) E do14:if p S and p is normal then15:gj gj 116:else17:if p S and p is spam then18:sj sj 119:else20:uj uj 121:end if22:end if23:end for24:m gj sj uj 3;25:bj gj /m, dj sj /m, nj uj /m, ej 3/m;26:M [i][j] (bj , dj , nj , ej );27:end for28: end for29: return M2.4Trust Propagation and CombinationGiven two edges e(i, s) and e(s, j) E with the weightsωis (bis , dis , nis , eis ) and ωsj (bsj , dsj , nsj , esj ), weare able to compute ωij (ωis , ωsj ). In other words, s’sopinion on the trustworthiness of website j can be propagated to website i so that i derives its own opinion aboutj ’s trustworthiness. The above-mentioned process is calltrust propagation in social networks. To distinguish fromdirect opinions, we use Ωij to denote i’s indirect opinionon j . In this way, Ωij can be computed from the followingequations [21]. bij bis bsj dij bis dsj,(2)n 1 bij dij esj ijeij ewhere e esj if eis 6 1, otherwise, e 1. That implies theprior uncertainty in i’s opinion on j is determined by that ofωsj if ωsj is not uncertain; otherwise, ωij will be uncertain.Note that ωis and ωsj can be replaced by indirect opinionsΩis and Ωsj .If there are several different paths from website i towebsite j , we can combine these opinions. Let Ω1ij 4(b1ij , d1ij , n1ij , e1ij ) and Ω2ij (b2ij , d2ij , n2ij , e2ij ) be two different opinions derived from two parallel paths from i to j .Then, a new opinion Ωij (bij , dij , nij , eij ) can be generated by the combining operation Θ(Ω1ij , Ω2ij ) as follows [21]: e2 b1 e1 b2 bij 1 ij ij2 ij1 ij 2 eij eij eij eij e2ij d1ij e1ij d2ij dij e1 e2 e1 e2ijijij ij.(3)2 11 2 n eij nij eij nij ij e1ij e2ij e1ij e2ij e1ij e2ij e ije1ij e2ij e1ij e2ijFor a computed opinion Ωij (bij , dij , nij , eij ), itcontains four values and cannot be directly used to sortwebsites. We need to convert it to a single trust value.The Eq. 4 is used to calculate the probability that j is atrustworthy website, where x and y are the coefficients ofposterior uncertainty and prior uncertainty, indicating howmuch of the posterior uncertainty and prior uncertainty arecredible, respectively.E(Ωij ) bij x nij y eij2.5(4)Enhanced OpinionWalk AlgorithmBased on the previous discussion, opinions are used toquantify the trust relations between individual websites.Specifically, the opinions are derived from the labeled websites, based on formula (1). With these trust opinions, theopinion matrix can be initialized that reflects the socialconnections among websites and the strength of these connections. OpinionWalk algorithm starts from a seed nodeto search the network level by level, and the trustworthiness of all websites are iteratively obtained during thesearching process. The trust computation is then realizedby carrying out propagating and combining operations onopinions. However, the OpinionWalk algorithm updates thetrustworthiness of all websites iteratively and every opinionneeds to be recalculated in each iteration. Let’s assume thealgorithm starts from website i and aims at computing thetrustworthiness of all other websites. The trustworthinessvalues are recorded in(k)Yi(k)(k)(k)(k) [Ωi1 , Ωi2 , · · · , Ωij , · · · , Ωin ]T ,(k)where Ωij denotes i’s opinion about the trustworthinessof website j , after the algorithm searches k levels in thenetwork. As a result, the execution time of OpinionWalkis not favorable for quick trustworthy website detection.To address this issue, in this section, we introduce the Enhanced OpinionWalk (EOW) algorithm that updates feweropinions in each iteration, and thus results in a shorterrunning time.When the algorithm starts from website i, the opinion(1)vectorY [ω , ω , · · · , ω , · · · , ω ]Tii1i2ijinis initialized, based on the direct links among websites.(k 1)(k)Next, we show how to obtain Yifrom Yi , whichoccurs when the algorithm moves from the k -th level to(k)(k 1)-th level in the network. For a trust opinion in Yi ,2327-4697 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TNSE.2018.2866066, IEEETransactions on Network Science and EngineeringTRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING(k)e.g., Ωis , if itwhere ωsj is not an uncertain opinion O and ωsj 6 OM and s 6 i 6 j , we can compute a(k)new opinion (Ωis , ωsj ), based on the trust propagationoperation. It denotes i’s opinion on the trustworthiness of j ,based on its k -hop “friend” website s’s “recommendation”.As shown in Fig. 2, if there exist m nodes that can make thistype of recommendation, labeled as s1 , s2 , · · · , sm , we cancombine the m newly obtained opinions to get a new opin(k)(k)(k)ion Θ( (Ωis1 , ωs1 j ), (Ωis2 , ωs2 j ), · · · , (Ωism , ωsm j )). Asthe opinion expresses i’s most current opinion on j ’s trust(k 1)worthiness, we denote it as Ωij. In the same way, we can(k)update all elements in Yi(k 1)to form Yis1 ߱௦ଵ s2i}sm߱௦ଶ 5(1)Ω13(1)Ω14and F (1) [0, 0, 1, 1]T that meansandwill be(1)(1)updated next but Ω11 and Ω12 remain the same, whenEOW searches the second level of the network. For node 3,(1)there is an opinion ω12 Y1 , and an opinion ω23 M ,we can update node 1’s opinion on node 3 via node2 to (ω12 , ω23 ). Similarly, because there is an opinion(1)ω11 Y1 and ω13 M , node 1 gets a new opinion onnode 3 as follows. (ω11 , ω13 ) (I, ω13 ) ω13.These two newly obtained opinion will be combined to formnode 1’s most current opinion on the node 3’s trustworthiness.(2)Ω13 Θ(ω13 , (ω12 , ω23 ))jFor node 4, we have ω12 Y1 and ω24 M , node 1’sopinion on node 4 is updated to (ω12 , ω24 ). With ω13 (1)Y1 and ω34 M , node 1 gets another opinion on node 4,i.e. (ω13 , ω34 ). Combining these two opinions yields(1)߱௦ (2)Ω14 Θ( (ω12 , ω24 ), (ω13 , ω34 )).Fig. 2: Illustration of trustworthiness update from k -th levelto (k 1)-th level in the network.(k 1)From the above description, we can see that Yi(k)is solely determined by Yiand M , and not all opin(k)ions are changed in the updating process. In fact, if Ωijchanges when the algorithm is processing the k -th levelof the network, then only i’s opinions on j ’s adjacentnodes need to be recalculated in the next iteration. Wepropose a mechanism to keep track of which elements in the(k)opinion vector Yineed to be updated and only update(k 1)those opinions in Yi. In the enhanced OpinionWalk(EOW) algorithm, there exists a Boolean vector F (k) [f1 , f2 , · · · , fj , · · · , fn ]T that indicates whether i’s opinionon j needs to be updated in the (k 1) th iteration. If fj(k 1)equals to 1, Ωijneeds to be recalculated and unchangedotherwise. With the subtle modification on the OpinionWalkalgorithm, the (average) execution time of EOW is only72.9% of OpinionWalk’s. We will use the example shownTherefore, after EOW algorithm finishes searching the sec(2)ond level, the opinion vector is updated to Y1 :T[I, ω12 , Θ(ω13 , (ω12 , ω23 )), Θ( (ω12 , ω24 ), (ω13 , ω34 ))]After this iteration, because Ω13 and Ω14 change, weneed to update the Boolean vector to F (2) [0, 0, 0, 1]Tindicating node 1 will update its opinion on node 4 but keepits opinions on other nodes unchanged, in the next round.This is because node 4 is the adjacent neighbor of node 3.When EOW searches the third level, because there exist(2)ω12 Y1 and ω24 M , we update Ω14 to (ω12 , ω24 ).(2)(2)With Ω13 Y1 and ω34 M , node 1 has a new opinion(2)on 4, (Ω13 , ω34 ). Combining these two opinions, node 1derives a new opinion on node 4 as follow.(3)(2)Ω14 Θ( (ω12 , ω24 ), (Ω13 , ω34 )).As such the opinion vector is update toih(3) T(2)(3) [I, ω12 , Θ(ω13 , (ω12 , ω23 )) ,Y1 I, ω12 , Ω13 , Ω14T1߱ଵଶ߱ଵଷ2߱ଶଷ3Θ( (ω12 , ω24 ), (Θ(ω13 , (ω12 , ω23 )), ω34 ))]߱ଶସ4߱ଷସFig. 3: An example of illustrating the Enhanced OpinionWalk algorithm.in Fig. 3 to illustrate how the EOW algorithm works. Withthe given network, we derive the opinion matrix as follows. I ω12 ω13 O OIω23 ω24 .M O OIω34 O OOILet’s assume EOW starts from node 1, then we have(1)Y1T [I, ω12 , ω13 , O] ,After this iteration, because node 4 has no adjacent node,we have F (3) [0, 0, 0, 0]T . That also means the EOW algorithm stops and node 1’s opinions on the trustworthiness ofall other nodes are obtained.Algorithm 2 describes how to get the trustworthinessof all other websites, from website i’s perspective. Line 1calls Algorithm 1 to obtain the opinion matrix M . Lines(1)2-5 initialize F and Yi , based on M . Lines 6-12 updatethe bit corresponding to i’s adjacent nodes to 1. Line 13initializes the searching level k to 1. Line 14 controls howmany levels that EOW algorithm will search on the graph(k 1)(k)G. Lines 15-29 compute Yibased on Yi and M , andupdate the Boolean vector F accordingly. Line 15 copies(k)(k 1)all opinions from Yito Yi. Lines 16-21 recalculatenode i’s opinions on the websites whose trustworthinessneed to be updated. Lines 18-20 combine all opinions derived from ωsj 6 O. Lines 22-29 update F [j] based on2327-4697 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TNSE.2018.2866066, IEEETransactions on Network Science and EngineeringTRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING(k 1)the information of which element in Yi[j] is different(k)(k)from that of Yi [j]. Finally, the vector Yiwill containnode i’s opinions on all other nodes, after EOW searchesH levels within the graph G. By increasing the value ofH , more accurate trust computation is expected, however,it will increase the execution time of the EOW algorithm.In practice, the value H is set to be a n

Considering websites as users, a hyperlink network can be modeled as a "social network" that reflects the "social connections" among different websites. The connection be-tween two linked websites can be assigned a weight to indicate the trustworthiness between them, which results in a weighted trust social network. Within the network,