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.
Please enter the password.
Submit

Change Nickname

Current Nickname:
Submit

Apply New License

License Detail

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

The MAC address of the server you want to deploy.

Please complete this required field.

Please complete this required field.

Cancel
Apply
ID
Product
Status
Cores
Applied Validity Period(days)
Effective Date
Excpired Date
Mac Address
Apply Comment
Review Comment
Close
Profile
  • Full Name:
  • Phone:
  • Company:
  • Company Email:
  • Country:
  • Language:
Change Password
Apply

You have no license application record.

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

Not having one? Apply now! >>>

Product Created On ID Amount (USD) Invoice
Product Created On ID Amount (USD) Invoice

No Invoice

Search
    English

      SybilRank

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

      Overview

      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.

      Concepts

      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; low-ranked nodes as are screened out as 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.

      Considerations

      • Each self-loop adds two degrees to its subject node.
      • 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.

      Syntax

      • Command: algo(sybil_rank)
      • Parameters:
      Name
      Type
      Spec
      Default
      Optional
      Description
      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

      Examples

      The example graph is as follows:

      File Writeback

      Spec Content
      filename _id,rank
      algo(sybil_rank).params({
        total_trust: 100,
        trust_seeds: [2,3,5],
        loop_num: 4
      }).write({
        file:{
          filename: "sybilRank"
        }
      })
      

      Results: File sybilRank

      S1,0
      S4,3.61111
      S2,4.45602
      S3,4.71065
      H9,5.0434
      H8,5.09259
      H4,6.66667
      H10,7.87037
      H5,8.67766
      H1,9.59491
      H2,9.9537
      H7,10.4167
      H3,11.305
      H6,12.6013
      

      Property Writeback

      Spec Content Write to Data Type
      property rank Node property float
      algo(sybil_rank).params({
        total_trust: 100,
        trust_seeds: [2,3,5],
        loop_num: 4
      }).write({
        db:{
          property: "trust"
        }
      })
      

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

      Direct Return

      Alias Ordinal Type
      Description
      Columns
      0 []perNode Node and its trust _uuid, rank
      algo(sybil_rank).params({
        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
      Description
      Columns
      0 []perNode Node and its trust _uuid, rank
      algo(sybil_rank).params({
        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
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写