What is a good measure of strength of a link and influence of a node?

Question

In the context of social networks, what is a good measure of strength of a link between two nodes? I am currently thinking that the following should give me what I want:

For two nodes A and B:
Strength(A,B) = (neighbors(A) intersection neighbors(B))/neighbors(A)

where neighbors(X) gives the total number of nodes directly connected to X and the intersection operation above gives the number of nodes that are connected to both A and B.

Of course, Strength(A,B) != Strength(B,A).

Now knowing this, is there a good way to determine the influence of a node? I was initially using the Degree Centrality of a node to determine its "influence" but I somehow think its not a good idea because just because a node has a lot of outgoing links does not mean anything. Those links should be powerful as well. In that case, maybe using an aggregate of the strengths of each node connected to this node is a good idea to estimate its influence? Am I in the right direction? Does anyone have any suggestions?

My Philosophy (and understanding of the terms):

• Strength indicates how far A is willing to do what B has already done
• Influence indicates how far A can make B do something (persuasion perhaps?)

Constraints: Access to only a subgraph. I mean, I am trying to be realistic here because social networks are huge and having a complete view is not so practical.

Answer 1

Few thoughts on this:

When you talk about influence of a node in a graph one centrality measurement that comes to mind it closeness centrality. Closeness centrality looks at the number of shortest paths in a graph the node is on. From an influence point of view, the node that is on the most shortest paths is the node that can share information the easiest, ie its nearer to more nodes than any other.

You also mention using the strengths of each node connected to a node. Maybe you should look at eigenvector centrality which ranks a node highly if its connected to other high degree nodes. This is an undirected version of PageRank.

Some questions that might affect you choice here are:

1. Is you graph directed?
2. Do you edges have weight? You mention strength... do you mean weights of some kind?

If you do have weights maybe the next step from a simple degree centrality would be to try a weighted degree centrality approach. Thus, just having a high number of connections doesn't automatically make you the most influential.

Answer 2

you might want to check out some more sophisticated notions of distance. A really cool one is "resistance distance", which lets you view distance as how likely a random path from one node will lead you to another

there are several days of lecture notes plus references to further reading at http://www.cs.yale.edu/homes/spielman/462/.