# SybilHP: Sybil Detection in Directed Social Networks with Adaptive Homophily Prediction
## 4 Methodology
### Redefine Potential Function  
Finally, we integrate the results derived from the previous sections into our edge-potential design. For unidirectional edge \((u,v)\), considering that message passing in the LBP algorithm goes both ways, we make our potential function direction sensitive based on the initial homophily strength parameters and then involve the adaptive homophily estimators to adapt to characteristics of nodes. Existing work [20; 21] assumes that a Sybil's following behavior is unpredictable. So, from a Sybil tail \(u\)'s standpoint, we cannot gain much effective information about the head's state. Similarly, if a benign user is being followed, chances are slim that one could infer the follower's state. Therefore, in these cases, we only use the initial homophily strength parameters \(\overrightarrow{w}_{s}\) and \(\overleftarrow{w_{b}}\) for a rough estimation of the benign head and the Sybil tail's homophily strength as shown in Figure 5(1,3), respectively. Dynamic homophily estimators \(c_{u,b}^{(t)}\) and \(c_{u,s}^{(t)}\) can be applied to weaken the homophily-based inference for \"dumb\" benign nodes who always follow Sybils and enhance the heterogeneity-based inference for \"enticing\" Sybil nodes who have plenty benign followers. In each iteration, they are updated to further elaborate the initial homophily strength \(\overrightarrow{w}_{b}^{*}\) and \(\overleftarrow{w_{s}}\) according to the nodes' preferences as shown in Figure 5(2,4). Formally, we have unidirectional edge-potential functions as follows. When sending a message from tail \(u\) to head \(v\) of a unidirectional edge, we have \(\overrightarrow{\varphi}^{(t)}(x_{u},x_{v})\) design:  
\[\overrightarrow{\varphi}^{(t)}(x_{u},x_{v})=\left\{ \begin{array}{ll} \overrightarrow{w}_{b}^{*}c_{u,b^{\prime}}^{(t)}&x_{u}=-1,x_{v}=-1\\ 1-\overrightarrow{w}_{b}^{*}c_{u,b^{\prime}}^{(t)}&x_{u}=-1,x_{v}=1\\ \overrightarrow{w}_{s},&x_{u}=1,x_{v}=1\\ 1-\overrightarrow{w}_{s},&x_{u}=1,x_{v}=-1.\end{array} \right. \tag{10}\]  
Figure 4: Homophily estimator for the edge incident with a benign tail or a Sybil head. Figure 5: Initial homophily strength parameters and adaptive homophily estimators for potential function. When sending a message from head \(u\) to tail \(v\), \(\overleftarrow{\varphi}^{(t)}(x_{u},x_{v})\) follows:  
\[\overleftarrow{\varphi}^{(t)}(x_{u},x_{v})=\left\{ \begin{array}{ll} \overleftarrow{w}_{b},&x_{v}=-1,x_{u}=-1\\ 1-\overleftarrow{w}_{b},&x_{v}=-1,x_{u}=1\\ \overleftarrow{w}_{s}c_{u,s}^{(t)},&x_{v}=1,x_{u}=1\\ 1-\overleftarrow{w}_{s}c_{u,s}^{(t)},&x_{v}=1,x_{u}=-1.\end{array} \right. \tag{11}\]  
For bidirectional edges, we adopt homophily strength \(\overleftarrow{w}\) with the following modification:  
\[\overleftarrow{\varphi}^{(t)}(x_{u},x_{v})=\left\{ \begin{array}{ll}\frac{1} {2}\overleftarrow{w}\left(c_{u,b}^{(t)}+c_{v,b}^{(t)}\right),&x_{u}=-1,x_{v}= -1\\ 1-\frac{1}{2}\overleftarrow{w}\left(c_{u,b}^{(t)}+c_{v,s}^{(t)}\right),&x_{u} =-1,x_{v}=1\\ \frac{1}{2}\overleftarrow{w}\left(c_{u,s}^{(t)}+c_{v,s}^{(t)}\right),&x_{u}=1,x _{v}=1\\ 1-\frac{1}{2}\overleftarrow{w}\left(c_{u,s}^{(t)}+c_{v,b}^{(t)}\right),&x_{u}= 1,x_{v}=-1.\end{array} \right. \tag{12}\]  
To sum up, we have the following direction-sensitive edge-potential design:  
\[\varphi^{(t)}(x_{u},x_{v})=\left\{ \begin{array}{ll}\overleftarrow{\varphi}^{ (t)}(x_{u},x_{v}),&\text{if $(u,v)$ bidirectional}\\ \overrightarrow{\varphi}^{(t)}(x_{u},x_{v}),&\text{if $(u,v)$ unidirectional}\\ \overleftarrow{\varphi}^{(t)}(x_{u},x_{v}),&\text{if $(v,u)$ unidirectional}.\end{array} \right. \tag{13}\]  
Integrated with the proposed edge-potential function \(\varphi^{(t)}(x_{u},x_{v})\), the pMRF model along with the LBP algorithm forms SybilHP. Given the social graph and a training set, SybilHP returns the posterior probability of nodes being Sybil in graph \(G\) for further classification or ranking tasks. Algorithm 1 summarizes the pseudo-code of SybilHP, from which, we can see that the time complexity of SybilHP is \(O(iter\cdot|E|)\).