-
@ david
2025-02-14 20:10:10
nostr:npub176p7sup477k5738qhxx0hk2n0cty2k5je5uvalzvkvwmw4tltmeqw7vgup there is a conversation we were having about centrality algorithms, I can’t find it, but I want to pick up where we left off.
Previous convo: PageRank is based on linear equations, which means we can use linear algebra to solve exactly in one step. Fast and efficient.
I argue that in many instances, we are going to want to incorporate nonlinear terms into our centrality algorithms. These trust scores will be more useful for many important purposes, like calculating trust-weighted averaging or trust-weighted sums, but the disadvantage is that we won’t be able to solve it as quickly and efficiently. Instead, we may need in some instances to iterate until convergence to within some acceptable margin of error.
As an example, suppose we want to do a trust-weighted average of 5-star ratings of widgets. What do we use for the weights? We could use personalized PageRank (pPR) as the weight, which will do a good job of screening out the spam and bots because their pPR scores will be low or zero. The problem is that this method will mean that the vote of someone like Dorsey, who has a zillion trusted followers, counts a lot more than an influencer who has half a zillion, which counts more than a pleb who has let’s say 500, which counts more than a newcomer who has 20. But arguably, it would make more sense to give equal weighting to Dorsey, the influencer, the pleb, and the newcomer. Why? Because we can be fairly certain that none of them are bots, and that they’re probably all real nostr users, and that’s all we care about in this particular hypothetical.
So your solution to the above is to use pPR but to select a cutoff and assign weight = 1 for anyone whose pPR score is above the cutoff, 0 for anyone whose score is below. I think that solution would be workable, albeit imperfect. This is where our convo left off.
My next observation: what you have described is a step function. Which, as you know, is nonlinear. And this is my basic point: We’re going to need nonlinear functions in our algos sooner or later, this is of fundamental importance, and there’s no way around it.
Also: it’s not clear where exactly the cutoff should be. Does it really make sense to give full weight to someone whose pPR score is cutoff + delta, but zero weight to someone whose pPR score is cutoff minus delta? Perhaps it would make more sense to replace the step function with something like an S-curve. How tight we make the S curve can be open for discussion.
So as I write this, I think: maybe there’s a way to have the best of both worlds. Instead of doing some large number N of iterations using a nonlinear function, we could have step 1 be to solve the linear algo exactly, then step 2 to be a single iteration of a nonlinear function, like the step function or S curve. Then when we have the luxury of taking a lot of time for calculations, and when we have a use case that benefits, that’s when we do the large number N of iterations of nonlinear function.
So those are my thoughts.