Is the ID or the number of interactions of that ID called the "degree"?

If ID=degree, this is quite a complicated problem. kyle's solution counts interactions and will get you part of the way. But counting occurrences of the ID from pairs is much more complicated. To see why consider these two star graphs. In graph I, node A has 1 occurrence and 4 interactions. In graph II, it has two occurrences and 8 interactions.

Graph I         
-------         
     X1
     |
X4 - A -  X2    
     |
     X3

Pairs: 
X1,A
X2,A
X3,A
X4,A  

Graph II         
--------         
     X1             Y1
     |              |
X4 - A -  X2 - Y4 - A - Y2     
     |              |
     X3             Y3

Pairs: 
X1,A   Y1,A   X2,Y4
X2,A   Y2,A
X3,A   Y3,A
X4,A   Y4,A
[download]

Distinguishing between multiple paths to the same occurrence and multiple paths to two occurrences requires analysis of entire paths, not just pairs. What makes Graph II have 2 occurrences of A is the fact that there is no way to start at X1 and reach the edge nodes Y1, Y2, or Y3 without passing through a second occurrence of A.

Best, beth

Update:made explicit my original (mis?)reading of the question.