I came across this paper that uses link anomaly detection to predict trending topics, and I found it incredibly intriguing: The paper is "Discovering Emerging Topics in Social Streams via Link Anomaly Detection".

I would love to replicate it on a different data set, but I'm not familiar enough with the methods to know how to use them. Let's say I have a series of snapshots of network of nodes across a period of six months. The nodes have a long-tailed degree distribution, with most having only a few connections, but some having a great many. New nodes appear within this time period.

How could I implement sequentially discounted normalized maximum likelihood calculations used in the paper to detect anomalous links that I think might be precursors to a burst? Are there other methods that would be more appropriate?

I ask both theoretically and practically. If someone could point me to a way to implement this in python or R, that would be very helpful.

Anyone? I know you smart folks out there have some starting thoughts for an answer,

  • 2
    $\begingroup$ If you don't mind relaxing the R/python preference, may be this work of mine can help? goo.gl/l7SLlB Some of the advantages of this method are that you don't need to worry about types of features, normalizations and more. $\endgroup$
    – arielf
    Sep 8, 2014 at 2:42
  • 3
    $\begingroup$ Unless I misunderstand the question, you should be able to implement the method from the paper the same way the authors of the paper implemented the method. If the method is not reproducible from the paper, then you should contact the authors. The authors may also be willing to supply their code. If you have specific theoretical questions or programming questions then they should be asked separately. $\endgroup$
    – Nat
    May 18, 2018 at 17:11

1 Answer 1


You should first come up with your definition of anomaly-score for a new node(see section 3.1, 3.2). Fortunately, the correspondence between a new post(in their case) and a new node(in your case) is almost one-to-one, since we are only interested in the set of nodes(users) that the node(post) is related to.

Thus, we can characterise a new node by the number of edges/connections k it has, and the set V of the other nodes it is connected to. Therefore, equations (1)-(4) could be written in a similar fashion. Then, you could use the Chinese Restaurant process, as described at the end of subsection 3.1., after introducing a new parameter $\gamma$. Now, given that you have obtained the probabilities (3), you can obtain the link-anomaly score (7).

Ask further, if you have difficulties to follow the steps described in subsection 3.4., where SDNML is applied.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.