As far as alternative heuristics to determining individual user's influence, I'm reminded of Malcolm Gladwell's "The Tipping Point", when he's describing the three archetypes of users: connectors, mavens, and salesmen. "Degree centrality" would seem to describe the main asset of connectors; I'd be interested to see if there are any good heuristics to find the other two types of influencers—the people with less friends, but bigger influence. After all, we all have app whores in our network, and we probably tend to tune them out over time.
Great read, by the way :)
Jesse Farmer
· 7 months ago
Hey Matt,
Glad you liked it and thanks so much for commenting.
A more general notion of influence is captured by eigenvalue centrality, which is similar to PageRank — every person's influence is proportional to the sum of their follower's influence. This sets up an eigenvalue problem, whose principal eigenvector contains the "influence" of each of the nodes.
The nice thing about Kempe's algorithm is that it sidesteps all these issues and just asks the question directly: if we influence this user, how many other people can we expect to be influenced as a result of the cascade? That seems like a pretty objective measure of influence, although it's computationally difficult.
The downside to both of these is that they require extensive knowledge about the underlying graph and diffusion processes, which we don't always have access to. I've sent an email to Kempe asking about this. I hope he responds!
one of the problems they are trying to solve is how information propogates over social networks/ blogs ? - for eg - consider the blogosphere as a directed graph - with blogs citing other blogs - given this which top N blogs should you read to keep yourselves abreast of information in a particular area
another sub topic is how does influence propogate over social networks - say you can give a sample of your product to only N people - which of them should you target given the social graph and influence of one node on the other
Hope this helps !
Cheers, Sagar
josephinebl
· 7 months ago
Hey Jesse! I´m happy that I randomly ran into you when my teacher recommended your blog. Although he was refering to one of your old articles.. anyhow! your passion is affecting my studies in a great way. thank youuu
Nishant
· 5 months ago
Hi Jesse, I just came across your site while I was searching for more details on the influence function. You have mentioned that "calculating the influence function exactly is NP-hard" - where did you come to that conclusion from? The Kempe paper you mentioned (ICALP '05) specifies that *maximizing* the influence function is NP-hard and they came up with a greedy strategy to approximate it. Could you please clarify? Thanks!
Jesse Farmer
· 4 months ago
Nishant,
You're correct!
My sentence doesn't even make much sense, IMO. What is "calculating the influence function exactly?" Do I mean determining the value of σ(A) for all A? Do I mean given a subset, A, calculating σ(A)?
I don't remember what I was thinking when I wrote it, honestly. :)
All Comments
Great read, by the way :)
Glad you liked it and thanks so much for commenting.
A more general notion of influence is captured by eigenvalue centrality, which is similar to PageRank — every person's influence is proportional to the sum of their follower's influence. This sets up an eigenvalue problem, whose principal eigenvector contains the "influence" of each of the nodes.
The nice thing about Kempe's algorithm is that it sidesteps all these issues and just asks the question directly: if we influence this user, how many other people can we expect to be influenced as a result of the cascade? That seems like a pretty objective measure of influence, although it's computationally difficult.
The downside to both of these is that they require extensive knowledge about the underlying graph and diffusion processes, which we don't always have access to. I've sent an email to Kempe asking about this. I hope he responds!
and some of the papers at http://www.cs.cmu.edu/~jure/research.html
Thanks for commenting. That does look interesting!
It looks like their project is mostly about instrumenting a network to detect cascades. Is that right?
one of the problems they are trying to solve is how information propogates over social networks/ blogs ? - for eg - consider the blogosphere as a directed graph - with blogs citing other blogs - given this which top N blogs should you read to keep yourselves abreast of information in a particular area
http://www.cs.cmu.edu/%7Ejure/pubs/blogs-sdm07.pdf
another sub topic is how does influence propogate over social networks - say you can give a sample of your product to only N people - which of them should you target given the social graph and influence of one node on the other
Hope this helps !
Cheers,
Sagar
I just came across your site while I was searching for more details on the influence function. You have mentioned that "calculating the influence function exactly is NP-hard" - where did you come to that conclusion from? The Kempe paper you mentioned (ICALP '05) specifies that *maximizing* the influence function is NP-hard and they came up with a greedy strategy to approximate it.
Could you please clarify?
Thanks!
You're correct!
My sentence doesn't even make much sense, IMO. What is "calculating the influence function exactly?" Do I mean determining the value of σ(A) for all A? Do I mean given a subset, A, calculating σ(A)?
I don't remember what I was thinking when I wrote it, honestly. :)