Open Sourcing of UA

Repository

<p dir="auto"><span><a href="https://github.com/holgern/ua-python" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">https://github.com/holgern/ua-python <p dir="auto"><img src="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmTovm7vgABrcrFH4gTuYH9BEUq8HJCU9H8p8LLk7FtTh2/steem-ua.png" alt="steem-ua.png" srcset="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmTovm7vgABrcrFH4gTuYH9BEUq8HJCU9H8p8LLk7FtTh2/steem-ua.png 1x, https://images.hive.blog/1536x0/https://cdn.steemitimages.com/DQmTovm7vgABrcrFH4gTuYH9BEUq8HJCU9H8p8LLk7FtTh2/steem-ua.png 2x" /> <h3>user authority - a way to measure trust <p dir="auto">UA works on the assumption that a user follow when he want's to see new posts from the account he starts to follow in his feed. When an account has a high UA value, it means that the account is followed by many other accounts as it has produced good content. <p dir="auto">The whole thing doesn't work, though, since there are accounts that are followed by countless accounts without ever having produced any content at all. <p dir="auto">One solution to this problem is the establishment of trusted accounts. Only accounts that were followed direct or indirect by trusted accounts have a UA value higher than zero. Who should be set as a trusted account? This is not an easy task. As witnesses in the steem blockchain have been elected, witnesses can be seen as somehow trusted accounts. <p dir="auto"><img src="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmRS2K4tN4pLFhuLwyPjmYHR2bJ7VtaRK7pvQK6vFXDCZK/image.png" srcset="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmRS2K4tN4pLFhuLwyPjmYHR2bJ7VtaRK7pvQK6vFXDCZK/image.png 1x, https://images.hive.blog/1536x0/https://cdn.steemitimages.com/DQmRS2K4tN4pLFhuLwyPjmYHR2bJ7VtaRK7pvQK6vFXDCZK/image.png 2x" /> <p dir="auto">It can be seen on those figures from the paper "Combating Web Spam with TrustRank" from Z. Gyöngyi et al. how this works. Each trusted node gets an initial seed value, which propagates through the follow connection to followed accounts. The amount which is propagated depends on the number of following accounts. <p dir="auto">There is damping. This means that an account which is not directly followed by a trusted account can accumulate less UA than an account which is directly followed by a trusted account. <h3>Mathematics <p dir="auto">We are starting with a static score distribution <code>d which depends on the received witness votes (non-witnesses are set to zero) <pre><code>d = [] for d in accounts: if d is witness: d.append(witness_votes) else: d.append(0) <p dir="auto">The sum of d is normalized to 1 <pre><code>d = d/sum(d) <p dir="auto">Now the UA_raw value can be computed by: <pre><code>UA_raw = d while True: UA_raw = alpha * T * UA_raw + (1-alpha) * d <p dir="auto">where alpha is the decay factor and normally set to 0.85 and T is the transition matrix. <p dir="auto">T*UA_raw is a matrix multiplication and is implemented as: <pre><code>for a in accounts: new_value_a = 0 for follow_a in a["followers"]: new_value_a += UA_raw_old[follow_a] / len(accounts[follow_a]["following]) UA_raw_new[a] = alpha * new_value_a + (1-alpha) * d[a] <p dir="auto">The algorithm is now extended by a virtual omega account. Whenever an account is nobody following (also called dangling account), a virtual follow to the virtual omega account which is following itself is added: <pre><code>new_value_omega = 0 for follow_a in zero_followings: new_value_omega += UA_raw_old[follow_a] UA_raw_omega = alpha * new_value_omega <p dir="auto">Implementing the omega account is necessary, as without, the algorithm does not converge. <p dir="auto">The sum of UA_raw_new + UA_raw_omega is now 1. <h3>Example <p dir="auto">In this simple example, B is followed by A. B is a dangling account. When no omega account is added, the sum is not 1 for every iteration. The algorithm is stable after two steps. <div class="table-responsive"><table> <thead> <tr><th>step<th>A<th>B<th>sum <tbody> <tr><td>0<td>1<td>0<td>1 <tr><td>1<td>1 * 0.15<td>1 * 0.85<td>1 <tr><td>2<td>1 * 0.15<td>0.15 * 0.85<td>0.277 <p dir="auto">Now, the omega account is added and assure that the sum is always 1. Now B is followed by A and omega is followed by itself and B. <div class="table-responsive"><table> <thead> <tr><th>step<th>A<th>B<th>omega<th>sum <tbody> <tr><td>0<td>1<td>0<td>0<td>1 <tr><td>1<td>1 * 0.15<td>1 * 0.85<td>0<td>1 <tr><td>2<td>1 * 0.15<td>0.15 * 0.85<td>0.85 * 0.85<td>1 <tr><td>3<td>1 * 0.15<td>0.15 * 0.85<td>(0.85 * 0.85 + 0.15 * 0.85) * 0.85<td>1 <h4>Mapping UA_raw <p dir="auto">UA_raw_new is mapped to a logarithm scale by: <pre><code>def UA(x, N): score = math.log10(x * N + 1/N)*2 + 1 if score < 0: score = 0 if score > 10: score = 10 return round(score, 3) <h3>Technology Stack <p dir="auto">The calculation of UA is divided into the following scripts: <h3>streamCustomJsonOps.py <p dir="auto">In order to calculate UA, all follow connection of all account must be freeze for the calculation. Thus, fetching just the follower for each account using the API does not work as this would take several hours and the first fetched accounts have a different follow state than the last ones. <p dir="auto">The python script fetches all account creation operation and custom_json with follow id from the first block. By doing it this way, it is guaranteed that all follow connections for all accounts are known for the exact same time. The script parses account creation operation which are: <ul> <li>account_create <li>account_create_with_delegation <li>pow <li>pow2 <li>account_create_with_delegation <p dir="auto">and custom_json operation. <p dir="auto">When a new account operation was found, it is stored into the database: <pre><code>account_data = {"block_num": block_num, "type": type_id, "account_index": next_account_id, "account_name": account_name} <p dir="auto">Whenever a custom_json with id=follow is found it is stored in the database. Stored are follower, following, the what field and the current block number. <h4>build_follow_db.py <p dir="auto">This script goes through the stored account creation and follow/unfollow operation and stores the current follow network state for a specific time point. The generated database contains all available account names and ids, and all follow connections. <p dir="auto">In order to keep the database is small as possible, all follow connections are stored with the account number. Each follow is one data entry with: <pre><code>{"follower": follower, "following": following, "state": state, "block_num": data["block_num"]} <p dir="auto">where follower and following are the account ids. <p dir="auto">At the moment this database has 112,732,000 entries. For the calculation of UA, all follow connection are needed. As they cannot be stored into RAM, they need to be read out when need from the database. <p dir="auto">This process could be speeded up by storing the follow connection into a mongo database. The possibility to use a mongo database was added later and is optional. <p dir="auto">When setting <code>use_mongodb=True the accounts and its follower/followings are stored into a mongo database. This is the default setting. <h4>init_accounts_for_ua.py <p dir="auto">In this script, all parameter for UA calculation are reset and initialized. <h4>set_trusted_accounts.py <p dir="auto">Fetches all active witnesses and calculates the static score distribution for all accounts. <h4>build_ua3.py <p dir="auto">Implements the iterative loop to calculate UA_raw for all accounts. The calculation is stopped when 20 iterations are reached or when the difference between two iterations is smaller than 1e-8. <h4>ua_top100.py <p dir="auto">This script is used to rank all accounts and to calculate the top 100 accounts. <h3>Roadmap <p dir="auto">We will work on open sourcing more UA-related components and try to improve the documentation readability of the code. <h3>How to contribute <p dir="auto">Everyone can fork the repository and do a pull request. You can also contact us in our <a href="https://discord.gg/KpBNYGz" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">discord. <h4>GitHub Account <p dir="auto"><span><a href="https://github.com/holgern" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">https://github.com/holgern