O(n) algorithm to find a “publisher” in a social network
algorithm
Solution
If your data is presented as an adjacency matrix, then you can proceed as follows. Start by checking entry (1,2) in the matrix. If 1 follows 2 then 1 is not the publisher, and if 1 does not follow 2 then 2 is not the publisher. Remove whoever is not the publisher (1 or 2) and let X be the remaining node. Then check entry (X,3) in the matrix. Similarly you will get that either X is not the publisher or 3 is not the publisher. Remove whoever is not the publisher and then add node 4 and repeat. After you have repeated this process with all n nodes, you will be left with one candidate for the publisher. Then you can check the row and column for the candidate to verify that it is a true publisher. Total running time is O(n) for the entire algorithm, even though the adjacency matrix has size n^2.
Problem
I was asked a question how to find a "publisher" in a social network. Suppose the (simplified) social network only has "following" relationship between two users and one cannot follow himself. Then we define a "publisher" as a user who is followed by ALL other users but does not follow anyone. More specifically, given such a social network graph in the format of adjacency matrix, say NxN bool matrix, where cell[i,j] indicates whether or not user i follows user j. How to find out the publisher. What I can see is that there is at most one publisher could exist.(it's easy to prove: since publisher is followed by everyone else, then everyone else follows at least one user, so they are not publisher). I do come up with a naive solution: first scan column by column, if there is a all true column j (except for cell[j,j] of course), then scan row[j] to make sure it's all false. Obviously, the performance is O(n^2) for the naive algorithm cause we scan the whole matrix. However, I was told that there is an O(n) solution. I am kind of stuck at O(n). Any hints?