Change Password

Please enter the password.
Please enter the password. Between 8-64 characters. Not identical to your email address. Contain at least 3 of uppercase, lowercase, numbers, and special characters (such as @*&#).
Please enter the password.

Change Nickname

Current Nickname:


Certificate Issued at Valid until Serial No. File
Serial No. Valid until File

Not having one? Apply now! >>>


ProductName CreateTime ID Price File
ProductName CreateTime ID Price File


      ✓ File Writeback ✓ Property Writeback ✓ Direct Return ✓ Stream Return ✕ Stats


      The SybilRank algorithm ranks the trust of nodes by early-terminated random walks in the network, typically Online Social Network (OSN). The surge in popularity of OSNs has accompanied by the increasing Sybil attacks, under which a malicious attacker creates multiple fake accounts (Sybils), with the purposes of spamming, distributing malware, manipulating votes or view counts for niche content, and so on.

      SybilRank was proposed by Qiang Cao et al. in 2012, it is computationally efficient and can scale to large graphs.


      Threat Model and Trust Seeds

      SybilRank considers an OSN as an undirected graph, where each node corresponds to a user in the network, and each edge corresponds to a bilateral social relationship.

      In the threat model of SybilRank, all nodes are divided into two disjoint sets: non-Sybils H, and Sybils S. Denote the non-Sybil region GH as the subgraph induced by the set H, which includes all non-Sybils and edges among them. Similarly, the Sybil region GS is the subgraph induced by S. GH and GS are connected by attacks edges between Sybils and non-Sybils.

      Some nodes that are considered as non-Sybils are specified as trust seeds for the operation of SybilRank. Seeding trust on multiple nodes makes SybilRank robust to seed selection errors, as incorrectly designating a node that is Sybil or close to Sybils as a seed causes only a small fraction of the total trust to be initialized and propagated in the Sybil region.

      Below is an example of the threat model with trust seeds:

      An important assumption of SybilRank is that the number of attack edges is limited. Since SybilRank is designed for large scale attacks, where fake accounts are crafted and maintained at a low cost, and are thus unable to befriend many real users. It results in a sparse cut between GH and GS.

      Early-Terminated Random Walk

      In an undirected graph, if a random walk's transition probability to a neighbor node is uniformly distributed, when the number of steps is sufficient, the probability of landing at each node would converge to be proportional to its degree. The number of steps that a random walk needs to reach the stationary distribution is called the graph's mixing time.

      SybilRank relies on the observation that an early-terminated random walk starting from a non-Sybil node (trust seed) has higher landing probability to land at a non-Sybil node than a Sybil node, as the walk is unlikely to traverse one of the relatively few attack edges. That is to say, there is a significant difference between the mixing time of the non-Sybil region GH and the entire graph.

      SybilRank refers to the landing probability of each node as the node’s trust. SybilRank ranks nodes according to their trust scores; nodes with low trust scores are ranked higher, and they are potential faker users.

      Trust Propagation via Power Iteration

      SybilRank uses the technique of power iteration to efficiently calculate the landing probability of random walks in large graphs. Power iteration involves successive matrix multiplications where each element of the matrix represents the random walk transition probability from one node to a neighbor node. Each iteration computes the landing probability distribution over all nodes as the random walk proceeds by one step.

      In an undirected graph G = (V, E), initially a total trust TG is evenly distributed among all trust seeds. During each power iteration, a node first evenly distributes its trust to its neighbors; it then collects trust distributed by its neighbors and updates its own trust accordingly. The trust of node v in the i-th iteration is:

      where node u belongs to the neighbor set of node v, deg(u) is the degree of node u. The total amount of trust TG remains unchanged all the time.

      With sufficient power iterations, the trust of all nodes would converge to the stationary distribution:

      However, SybilRank terminates the power iteration after a number of steps before convergence, and it is suggested to be set as log(|V|). This number of iterations is sufficient to reach an approximately stationary distribution of trust over the fast-mixing non-Sybil region GH, but limits the trust escaping to the Sybil region GS, thus non-Sybils will be ranked higher than Sybils.

      In practice, the mixing time of GH is affected by many factors, so log(|V|) is only a reference, but it must be less than the mixing time of the whole graph.


      • Each self-loop adds two degrees to its subject node.
      • The SybilRank algorithm ignores the direction of edges but calculates them as undirected edges.
      • SybilRank’s computational cost is O(n log n). This is because each power iteration costs O(n), and it iterates O(log n) times. It is not related with the number of trust seeds.


      • Command: algo(sybil_rank)
      • Parameters:
      total_trust float >0 / No Total trust of the graph
      trust_seeds []_uuid / / Yes UUID of trust seeds, it is suggested to assign trust seeds for every community; all nodes are specified as trust seeds if not set
      loop_num int >0 5 Yes Number of iterations, it is suggested to set as log(|V|) (base-2)
      limit int >=-1 -1 Yes Number of results to return, -1 to return all results


      The example graph is as follows:

      File Writeback

      Spec Content
      filename _id,rank
        total_trust: 100,
        trust_seeds: [2,3,5],
        loop_num: 4
          filename: 'sybilRank'

      Results: File sybilRank


      Property Writeback

      Spec Content Write to Data Type
      property rank Node property float
        total_trust: 100,
        trust_seeds: [2,3,5],
        loop_num: 4
          property: 'trust'

      Results: Trust score for each node is written to a new property named trust

      Direct Return

      Alias Ordinal Type
      0 []perNode Node and its trust _uuid, rank
        total_trust: 100,
        trust_seeds: [2,3,5],
        loop_num: 4
      }) as trust 
      return trust

      Results: trust

      _uuid rank
      11 0.0000000
      14 3.6111109
      12 4.4560180
      13 4.7106481
      9 5.0434031
      8 5.0925918
      4 6.6666660
      10 7.8703699
      5 8.6776609
      1 9.5949059
      2 9.9537029
      7 10.416666
      3 11.304976
      6 12.601272

      Stream Return

      Alias Ordinal Type
      0 []perNode Node and its trust _uuid, rank
        total_trust: 100,
        trust_seeds: [2,3,5],
        loop_num: 4,
        limit: 4
      }).stream() as trust
      find().nodes({_uuid == trust._uuid}) as nodes
      return table(nodes._id, trust.rank)

      Results: table(nodes._id, trust.rank)

      nodes._id trust.rank
      S1 0.0000000
      S4 3.6111109
      S2 4.4560180
      S3 4.7106481
      Please complete the following information to download this book