hodlbod on Nostr: Great work pippellia , this is a must read. Implementing WoT well is critical for ...

Great work pippellia (nprofile…38t6) , this is a must read. Implementing WoT well is critical for making nostr live up to the promise.

One takeaway in particular I appreciated was the distinction between direct propagation, transposition, and co-citation as different ways to build out a trust graph. Coracle only uses direct propagation, but each method has different characteristics that can add nuance to recommendations.

Read it!

quoting nevent1q…t2pt

For reading the article with proper Latex, head over to [pippellia.com](https://pippellia.com/pippellia/Social+Graph/Navigating+the+social+graph)
#
# Introduction

The emergence of decentralized social networks with sovereign identities (e.g. [Nostr](e.g. [Nostr](https://nostr.com/)) is a pivotal moment for the web, and it comes at the perfect time. In the age of AI, where it's getting cheaper and cheaper to impersonate people, distort videos and images, or just make them up, how is it possible to know what's _true_? What does _truth_ even mean these days?

These are questions I will not attempt to answer. However, even if the ontology of truth has eluded philosophers forever, a more practical approach is needed if the Web is not to degenerate into a nihilistic place where nothing is real, or worse, a place where everything requires identity verification and the approval of a central authority.

In this paper, you will find a definition of the social graph, principles for thinking about it, and practical ideas for using it for DoS prevention, social discovery, anti-impersonation, accurate ratings, and more. You will also learn about alternative mechanisms that can be used in conjunction with social graph analysis to provide more compelling and complete solutions.

## Social Graph

First, what is a graph? A graph _G_ is a mathematical structure consisting of a set of nodes or vertices _V_ and a set of edges _E_.

In mathematical notation, we write _G = (V,E)_.

Edges are defined by a relation on the set _V x V = {(v,u) : v,u in V }_; for example, if node _v_ and node _u_ are related (e.g. _v_ follows _u_), then the pair _(v,u)_ is contained in the set _E_. In the notation

_E = { (v,u) in V^2 : v is related to u }_

The relationship can be symmetrical or asymmetrical, distinguishing between undirected and directed graphs.

A social graph is simply a graph in which the nodes are human entities (such as individuals, companies, groups, etc.) and the edges represent some form of social relationship, such as being friends with, following, or being zapped.

Before we go any further, we need to define another important notion, that of a neighborhood.

The neighborhood of a set of vertices _S_ subset of _V_ in _G_ is another set of vertices whose defining property is to be connected to a vertex in _S_. In mathematical notation

_N_G(S) = { u in V : exist s in S, (s,u) in E }_



What problem is the social graph solving? The answer is many, in many different ways and forms. We are talking about using it as a defense mechanism against impersonation, as a way to prevent DoS attacks, to facilitate social discovery and connections, and to calculate more accurate ratings. But before we dive into the implementations, I ask you to pause for a moment to understand the magnitude of what we are discussing.

# Principles

Don't fall into the trap of thinking that the engineers at YouTube were evil when they designed their algorithm. As the saying goes, the road to hell (read: open-mouth theater) is paved with good intentions (read: the desire to over-optimize engagement).



If your implementation is successful, people's behavior will be affected. That's why it's important to establish principles that can guide designers and developers in creating systems that are healthier than the world we're leaving behind.

## Principle of least interference

A good rule of thumb when designing systems that affect social dynamics is to follow the principle of least interference.

**Principle of least interference**: solve the _problem_ by implementing whatever mechanism has the least possible impact on social dynamics.

As an heuristic based on this principle, it is generally better to focus on solving only _one problem_ at a time, since it is unlikely that solving multiple problems at once will not lead to a greater impact on those social dynamics.

A great example to analyze is the WoT score implemented by [Coracle](https://coracle.tools/), which tries to "reduce spam, impostors, and objectionable content", all at once.


Let's start by analyzing how it works as an anti-impersonation mechanism.

If you search for 'Lyn Alden', it is very likely (if you are part of a "good" network) that the npub with the highest WoT is the real Lyn, while all others are impersonators.



However, a simple warning icon above all other Lyns would have accomplished the same goal without introducing a rating that can alter social dynamics.

In fact, the WoT score represents the opinion of the crowd around you, which doesn't offer any nuance when comparing the reputation of different real people. Crowd thinking is one of the biggest problems of the world we are leaving, and it would be a silly exercise to bring it with us.

Besides, we do not walk around with a number on our forehead in meatspace, nor should we in cyberspace, even if that number depends on the observer.

There is also another, more fundamental problem, which is that the user _v_ only has information about a limited subset of the network, namely _N_G^2(v) = N_G(N_G(v))_, where _G_ is the graph defined by the relation "follow OR mute" relation.

Therefore, if you set the WoT threshold above zero, you won't see anyone outside of _N_G^2(v)_, which certainly prevents spam, but at the cost of discoverability.

We'll come back to how to design a more effective anti-impersonation system later.

## Principle of Relativity in cyberspace

The current Web, and our societies in general, are built on an outdated paradigm that relies on and requires consensus about what is true, false, good, or bad. Unspeakable atrocities have been committed to achieve and maintain such consensus.

However, we must move beyond this legacy of the past if we are to usher in a new era of freedom.

_The notion of a commonly shared belief or social truth is as dead in this new millennium as God was in the 19th century._

**Principle of Relativity in Cyberspace**: You cannot and should not _dictate_ what is true or false, what is good content or bad content or spam, for another person.

If you do, you will simply be replacing the beast with a new set of beliefs. It's true that there are many different clients to choose from, but there were many different web browsers back in the day, and that didn't end well.

The reality is that a global agreement on things has seldom been necessary. In fact, _relative canonicality_ can be achieved without the need for a central authority.

[Wikifreedia](https://wikifreedia.vercel.app/) (a nostr alternative to Wikipedia, as you have probably guessed) fully embraces this idea of relative canonicality. Each topic contains multiple entries; there is no single source of truth that aims or claims to be neutral. Of course, this doesn't mean that all entries are equally good or useful. On the contrary, there is a very opinionated and biased way of sorting them, which depends on the observer. Regardless of the specific implementation (again, number on the forehead), this is the way to go, this is relativity in cyberspace.



## There is no Global

This point is arguably a corollary of the previous principle, but it's so important that it needs to be fully explained. The notion of global is also dead.

Despite being the largest indexer in the world, Google only indexes a small portion of the web. The engineering challenges behind indexing absolutely every person and piece of content in an ever-growing, open and hostile decentralized network will likely exacerbate this outcome: Nostr will outgrow every index.

As spammers become more sophisticated, crawlers will have to become more selective, limiting the percentage of the network that is indexed. Therefore, as a client designer or developer, you really only have a limited view of what's happening.

This reinforces the statement that you cannot decide for someone else what is good or bad, true or false. You can't possibly know, because what you have is a local, limited view, just like everyone else's.

Let's take [Nostr Band](https://stats.nostr.band) for example. As much as I appreciate their cool statistics, it's important to know their limitations. The version of [Trust Rank](http://infolab.stanford.edu/~zoltan/publications/gyongyi2004combating.pdf) that Nostr Band implements:

1. runs on the subset of the network they are aware of
2. uses an arbitrarily chosen set of NIP05 providers for determining the so called good seeds



This approach is fine if it's used to defend the service provider against spammers (see DoS prevention section for improvements).

However, such an arbitrary view (all are, but some less than others) shouldn't be imposed on the end user, but only used as a way for the service provider to select the customers it wants to serve.

## Principle of natural patterns

I believe that technology is made for people, so it should serve us and improve our quality of life. We shouldn't adapt to technology, technology should adapt to us.

This context is no exception to the rule. Humans are social creatures, and our social dynamics and behaviors have evolved through our long history. Therefore, before introducing new and artificial social dynamics, it's wiser to mimic the natural dynamics that have evolved with us for millennia.

**Principle of natural patterns**: When in doubt, try to mimic the social dynamics of meatspace

For example, in meatspace, a friend of a friend is not a stranger, but it's not a friend either. It's something in between, and a good candidate for a potential future friend.

Another example is something that will hit home if you've ever been to a bitcoin conference. When you're among people with the same interests, and I would argue mostly overlapping values, even if you've never met them, you can't say they're strangers.

Examples abound, so there is really no reason to try to impose any artificial dynamics before exhausting what nature has given us.

---

To summarize, we take from this section three principles that will inform our analysis and design decisions going forward:

- The principle of least interference
- The principle of relativity in cyberspace
- The principle of natural patterns


# The Problems

Finally, we can start discussing some concrete problems and ways to solve them. There are several well-defined problems that social graph analysis can help with. Again, it's important to define them well if we want to follow the principle of least interference.

The first problem we will analyze is protection against impersonation, one of the most important pieces to get right.

## Anti-impersonation

### Social endorsement

Who is the real Giacomo? In this case, it's pretty simple


First of all, let's talk about what won't help us decide:

- the name
- the profile picture
- the bio
- the date of creation


And no, not even the number of followers, as this is a completely irrelevant metric in an open and hostile network. [See an example](https://ron.stoner.com/I_Gained_1_Million_Followers_in_24_Hours/)

What helps us is the line below:

> "Followed by Bitcoin Africa Story, Nostr Wallet Connect, and 666 others you follow".

This is the signal. Follows can be faked, but follows from people you trust cannot be faked (or are more expensive to get). This is a particularly good design because it adheres to the principle of relativity in cyberspace. It doesn't _prescribe_ who the real Giacomo is, it doesn't _summarize_ the data for you (like the aforementioned WoT score, where every follower has the same weight), but it shows you clues that you can decide to interpret in the way you want.

The same idea can be applied to mutes, which gives you a few more clues.

Obviously, such a system can be extended not only to the people you follow, i.e. _N_G(v)_, but also to the people who are 2 hops away from you, i.e. _N_G^2(v) = N_G(N_G(V))_, or _n_ hops away from you, i.e. _N_G^n(v)_.

However, the signal becomes increasingly diluted and unreliable the farther you go.

This approach is a good start, but it can't really solve the impersonation problem on its own because it's limited in reach and suffers from a bootstrapping problem for new users, which is really the same problem if you think about it.

There is also a subtle issue worth mentioning. What if a reputable person tries to impersonate someone else? This attack is possible because it won't be detected immediately, but the more prominent the person, the faster this attack will be detected, causing the attacker to lose their hard-earned reputation.

Furthermore, for truly prominent figures such as heads of state, this problem can be mitigated (but not completely solved) by third-party credentials that can be displayed by clients.

### NIP05 providers
Another approach that has been tried is to rely on NIP05 providers. If I trust a NIP05 provider to verify the people they serve, then I can assign a non-zero level of trust to their customers. However, this approach obviously requires trust, which isn't ideal since there are trustless approaches that provide better guarantees.

### PoW keys

When we see a stranger enter the pub where we are, or when we are crowded on the subway, we find ourselves potentially vulnerable to strangers. In most civilized places, however, we don't live in a constant state of fear, and that comes from the fact that others are vulnerable as well. Everyone has skin in the game, even the aggressors, which means that the best way to play this game is not to mess with other people.

On Nostr, however, the only consequence you can feel is the loss of your reputation, which by definition is worthless when the npub is brand new.

However, there is a way to add skin in-game for new keys, i.e. PoW keys.

The process works like this: while creating your identity, your machine can generate a new private key _sk_ until the corresponding public key _pk_, as a binary number, satisfies the following inequality:

_pk <= t_ ; where _t_ is a threshold of your choice.

Since there is no efficient way to do this (allegedly), this process requires the expenditure of computing power and energy. This adds a quantifiable and verifiable cost to any identity, making credible impersonation expensive.

However, PoW keys can't work at scale, because:

1. they require **commitment at key creation**, which is bad UX because it reverses the "try before you buy" rule
2. the **PoW can't be updated** over time
3. It is not possible to delegate the work without delegating the key (supposedly)



The last point implies that the **economy of scale favors the attacker**, because they have multiple targets, whereas the defender can only defend himself.

However, there is a similar approach that offers what I believe are more appropriate tradeoffs: **PoW Endorsement**.

### PoW endorsment
A PoW endorsement is a simple unsigned user metadata event containing a target npub, a difficulty commitment threshold $t$, and a nonce.

The nonce is randomly generated until the following condition is satisfied:

_h(event) <= 2^t_ ; where _h_ is a cryptographic hash function such as SHA256

If the condition is met, the PoW endorsment is valid, and the target npub's "PoW weight" becomes _256 - t_.

What I am describing is basically [NIP13](https://github.com/nostr-protocol/nips/blob/master/13.md), except that it should use kind 0, and it doesn't need a signature (what's the problem if someone wants to add PoW to someone else's npub?).

What makes PoW endorsements different from PoW keys is that:

1. it doesn't require **any commitment at key creation**
2. the **PoW can be updated** over time
3. it's possible to **delegate the work** without delegating the key
4. **requires data availability**, because the work is separate from the key



Point 3 is what makes this approach feasible and scalable, especially for mobile devices constrained by CPU and battery limitations.

Point 4 isn't particularly bad because the events are small, public, and the user has an incentive to store them.

**Example of how it works**

- Alice gives a npub to the Miner
- Alice pays the Miner $10
- The Miner mines the PoW endorsement, with the target npub
- The target npub now has a non-zero PoW weight



**How does it help?**

If the target npub has a non-zero PoW weight, credible impersonation attempts require a cost. The attacker's social capital (PoW weight) becomes less and less valuable, and is eventually lost, as more people discover the attack and mute the attacker's npub.

Furthermore, _assuming that most of the PoW weight is allocated to real people (1)_, it's possible to use its distribution to fix the shortcomings of social endorsement.

For example, a new user can be presented with the choice of following the npubs with the highest [Trust Rank](http://infolab.stanford.edu/~zoltan/publications/gyongyi2004combating.pdf), where the good seeds are the npubs with non-zero PoW weight. The same principle can be applied to an existing user trying to get information about an npub that is many hops away from him/her.

If you want to summarize this idea to the maximum, if the number of followers is meaningless, that's not true for the number of followers with non-zero PoW weight (under assumption 1).

I have started working on this idea and preliminary results are promising, but more thought is needed

### Colored halo

Another anti-impersonation mechanism tried by [Nostrudel](https://next.nostrudel.ninja/#/) is to use a few characters of the public key (in hex format) to identify a unique color that is displayed around the user's profile picture.


The idea is that if I am already following the real Lyn, a credible impersonation attempt would require generating many times the key pair to get the same or very similar color. This requires energy, which means cost.

However, this information is only useful if I already follow the real Lyn and remember her color. Asking my trusted network for the color of a particular person is no different task than asking her npub directly.

This means that this approach, while interesting, is not very useful.

## DoS attack prevention

When analyzing Denial of Service attacks, we should distinguish between defense mechanisms that work at the network level, at the service provider level, and at the user level.

Talking about the first case may seem to contradict the principle of relativity in cyberspace, but here by network we mean any set of network participants who are willing to cooperate but not necessarily trust each other.



### Network level

PoW events basically apply the concept of [Hashcash](http://www.hashcash.org/papers/hashcash.pdf) not to email messages but to notes. There is not much to say here, except to note that the PoW can be outsourced to service providers that can most likely outcompete the attackers in efficiency.

### Service provider level

The best tool the service provider can use to prevent DoS is money. A paid service, either pay-per-use or subscription-based, can work both for monetization and as a defense mechanism. However, not every service (or sub-service) is directly monetizable, which is where social graph analysis can help.

The idea is to selectively choose which npubs are considered _potential good customers_ and filter out everyone else. If this needs to be said, I'll say it: _this is not censorship, this is simply a business deciding who to serve_.

Many different criteria can be used to select what is a good customer, especially since this definition depends on the service being provided.

A general approach is to use Trust Rank or [Spam Mass Estimates](http://infolab.stanford.edu/~zoltan/publications/gyongyi2006link-tr.pdf) (with a suitable measure for selecting the good seeds, such as PoW weight) as the criteria for deciding the "good customers". Those who don't qualify will simply not be served for free.

### User level

Here we consider a simple defense against DoS attacks on user DMs.

The user $v$ has a whitelist of npubs that can directly DM him/her for free. If the sender is not on the whitelist, the DM will only be displayed by the client if it is preceded by or comes with a payment above a certain threshold.

The whitelist can be edited manually, but it's automatically populated based on some social graph criteria that the user has approved.

For example, all npubs in _N_G(v) U N_G^2(v) U N_G^3(v)_ can be automatically added to the whitelist of user _v_.



## Personalized Ratings

The idea that every opinion or vote is equally important to everyone is a byproduct of political democracy and its sanctification. This is never the case in any social context.

Imagine you want to buy a product that has thousands of good reviews, but your friend recently bought it and tells you it's not good. It's natural for you to give more weight to your friend's opinion, contrary to the belief that each opinion has equal weight.

When computing an average, there is always an assumption about the *weight distribution*, i.e. how important each vote is.

Given a list of ratings _(r_i)_i_ and a weight distribution _(w_i)_i_ such that the sum of the weight is 1, the average is _sum r_i w_i_

The democratic average assumes each opinion has exactly the same weight.

Social graph analysis can be useful to design more accurate and even personalized ratings, i.e. ratings that reflect who the viewer is and what he/she is looking for at any given time.

For example, you might want to give more weight to people who have similar interests to you, or more weight to your friends and friends of your friends. Many different criteria for calculating weight distributions are possible, making this an exciting area for future research.

It's important to note that the most trustworthy ratings will be those that are independently verifiable, both in the ratings and in the weight distributions.

Practically speaking, there are two steps involved in computing a weight distribution:

- Select the support, i.e. the set of npubs that have a non-zero weight.
- Assigning a specific weight to each npub that is part of the support.



These two steps can be done simultaneously or one after the other. In the next section, we'll look at support selection, a problem that arises in another, seemingly unrelated context: social discovery.

## Social Discovery

How many times have you discovered something thanks to a friend's recommendation? This phenomenon can actually be productized to streamline the discovery of content, places, and people that are relevant to the end user.

Here is a mathematical formulation of the problem:

Consider a social graph _G = (V,E)_, where the nodes are ordered, i.e. _V = { v_1, v_2, ... v_n}_.

The goal is to construct another graph _G' = (V,E')_, where _E'_ consists of the recommendations for each of the users we want to serve. This is a simplified scenario, where what is being recommended are other nodes in the graph.

What we need is a function _f : G --> G'_ that takes _G_ as input and returns _G'_ as output, i.e. the recommendations we are interested in.

I'll now introduce a definition to simplify the problem.

**Adjaciency matrix:** Given a graph _G = (V,E)_, its edges can be represented as a matrix called the adjacency matrix _A_, defined as follows:

_A_ij = 1_ if and only if _v_i_ is related to _v_j_

In light of this new definition, the problem is to construct _f : A --> A'_, which is a function that takes an n by n boolean matrix _A_ as input and outputs the n by n recommendation matrix _A'_.

With this notation, the recommendation list of the node _v_i_ consists of the nodes corresponding to the non-zero elements of the i-th row of _A'_.





Look at the example in the picture. By applying an unknown (for now) function _f_, we get the recommendation matrix _A'_. Only the first row contains a non-zero element whose position is (1,3). This means that node _v_1_ has node _v_3_ as a recommendation.

There are _(2^{n^2})^{2^{n^2}}_ of such functions (exercise: why?), but only a few of them make sense and mimic the heuristics humans use.

The first social dynamic we want to replicate is the "friend of a friend" dynamic, or more specifically, if _v_i _follows _v_j_, and _v_j_ follows _v_k_, then _v_k_ is added to _v_i_'s recommendation list.

In other words, we want _A'_ij = 1_ if and only if _v_i_ is connected to _v_j _by a path of length exactly 2. In this case, we are not interested in how many such paths exist, but only in whether there is at least one.



This rule is encoded in the function _f: A --> A' = A @ A = A^2_, where _@_ is the product between [Boolean matrices](https://en.wikipedia.org/wiki/Boolean_matrix) ( exercise: check that it's correct).

Inspired by this simple yet powerful result, [previous research](https://snap.stanford.edu/class/cs224w-readings/guha04trust.pdf) has investigated the class of candidate functions _f_M: A --> A' = A @ M_.

Here are some examples of such matrices _M_.





Applying each of these functions to _f_M_ adds new relations to the graph, and this process can be repeated many times until the desired result is achieved.

For example, in the matrix _A + A^2 + A^3 + ... + A^m_, node _v_ is connected to node _u_ if and only if there exists a path of length _<= m_ from _v_ to _u_ in the original graph _G_.

Formulating the problem of social discovery as an iteration of atomic propagation rules has many advantages, since:

- It's simple, yet can accommodate many different propagation rules
- It's passive, since it doesn't require the user to specify anything other than the rules and the number of iterations desired
- It's efficient, since its space complexity takes advantage of the sparsity of social graphs, and its time complexity can be estimated to be _O(n^{5/2})_ (Learn more about the [time complexity of Boolean matrix multiplication](n^{5/2}) ).
- It's well supported by most programming languages, given how ubiquitous matrix multiplication is
- It's transparent and independently verifiable in its operations



Furthermore, as highlighted in the previous section, this approach is applicable to compute transparent and personalized weight distributions.

Considering again the direct propagation rule (friend of a friend), we can start assigning weights based on the distance to the user.

If the distance is 1, meaning a direct connection, the weight is set to 1. Whenever the distance increases by 1, the weight decreases by a factor of _gamma in [0,1]_, a parameter potentially chosen by the user.

On a practical level, this means that the service providers compute and store the matrices _A, A^2, ... A^m_ for a reasonable _m_.

Each user _v_i _can choose _gamma_i in [0,1]_, and _k_i <= m_, and the personalized weight distribution he/she gets is

_A_i + gamma_i A^2_i + ... gamma_i^{k_i-1} A^{k_i}_i_

with _A_i_ representing the i-th row of the matrix _A_.

- If _gamma_i = 0_, the user chooses to consider the ratings of only those he follows as relevant.
- If _gamma_i = 1_ and _k_i = m_, the user chooses to give basically the same weight to everyone in the network, and will get a democratic average rating.
- If _gamma_i = 0.5_, then the weight of direct followers is 1, that of two hops is 0.5, then 0.25 and so on.


By combining and experimenting with propagation rules and weighting criteria, it's possible to efficiently compute personalized, verifiable and dynamic ratings for each user, making this an exciting area for future development.

# Conclusion

This is a comprehensive yet superficial paper, as it touches on many different areas without exhausting any. This was done intentionally to stimulate interest in the field of social graph analysis. More importantly, it aims to help the reader understand the significant impact this exciting new field can have on the Web, although not without its risks.

----

Interested in implementing the social graph into your App? Reach out, I would be more than happy to help

---
For reading the article with proper Latex, head over to [pippellia.com](https://pippellia.com/pippellia/Social+Graph/Navigating+the+social+graph)