Navigating the social graph

For reading the article with proper Latex, head over to pippellia.com

Introduction

The emergence of decentralized social networks with sovereign identities (e.g. Nostr 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.

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

_NG(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, 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(NG(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 _NG^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 (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 for example. As much as I appreciate their cool statistics, it’s important to know their limitations. The version of Trust Rank that Nostr Band implements:

runs on the subset of the network they are aware of
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

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

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. _NG(v), but also to the people who are 2 hops away from you, i.e. _N_G^2(v) = N_G(NG(V)), or n hops away from you, i.e. _NG^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:

they require commitment at key creation, which is bad UX because it reverses the “try before you buy” rule
the PoW can’t be updated over time
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, 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:

it doesn’t require any commitment at key creation
the PoW can be updated over time
it’s possible to delegate the work without delegating the key
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, 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 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 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 (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 NG^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 wi

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.

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, … vn}.

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:

_Aij = 1 if and only if _vi is related to _vj

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 _vi 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 _v1 has node _v3 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 _vj, and _vj follows _vk, then _vk is added to _vi’s recommendation list.

In other words, we want _A’ij = 1 if and only if _vi 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 ( exercise: check that it’s correct).

Inspired by this simple yet powerful result, previous research has investigated the class of candidate functions _fM: A –> A’ = A @ M.

Here are some examples of such matrices M.

Applying each of these functions to _fM 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^{⁵⁄₂}) (Learn more about the time complexity of Boolean matrix multiplication ).
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 _gammai in [0,1], and _ki <= 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 _Ai representing the i-th row of the matrix A.

If _gammai = 0, the user chooses to consider the ratings of only those he follows as relevant.
If _gammai = 1 and _ki = m, the user chooses to give basically the same weight to everyone in the network, and will get a democratic average rating.
If _gammai = 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