I am looking for a way to the model the incidence of crime among a network of individuals. Part of it will use machine learning, and part of it will have to resort to some graph theoretic representation.


Consider the following individuals forming nodes in the larger network of society.


  • 62 years old, clean criminal record
  • married and father of two
  • works as a psychologist
  • pays his taxes
  • gives to charity


  • 36 years old
  • convicted of a DUI three years ago, but otherwise clean criminal record
  • works in a convenience store
  • married and no children
  • once had an addiction problem to cocaine


  • 42 years old
  • freshly released from a 20-year sentence for homicide
  • high school dropout
  • unemployed
  • is looking into dealing illegal drugs and guns

As should be "obvious", one could run some kind of machine learning on the bullet points for each of the individuals and obtain a score of "criminality risk". (The machine learning model could have been trained over several such labeled observations in society.) John would score lowest, Robert highest, and Ted somehow in the middle because of his troubled history. So on a crude risk scale from 0 to 2, we would have John = 0, Ted = 1, and Robert = 2.

So far, we've only looked at the standalone nodes and their intrinsic data (i.e., the bullet points above). However, we can assume that all three individuals can somehow interact, and that's where graph theory comes in. Examples of such interactions (Ix) could be:

  • I1: Robert sells cocaine to Ted.
  • I2: John buys a soda from Ted's convenience store.
  • I3: Robert goes to John for psychological counseling on reintegrating society.
  • I4: Robert asks Ted if he could work in his store.
  • I5: John buys an illegal gun from Robert.

In light of these interactions, the scores inferred from the bullet points need to be adjusted, namely:

  • I1: Ted's risk goes up. Robert's risk stays the same.
  • I2: John's and Ted's risks stay the same.
  • I3: Robert's risk goes down. John's risk stays the same.
  • I4: Robert's risk goes down. Ted's risk stays the same.
  • I5: John's risk goes up. Roberts's risk stays the same.

It's therefore clear that the direction and nature of the interaction matters in inferring the risk scores. Any graph that represents these interactions should also allow for cycles, so traditional Bayesian networks aren't an option. One should also have a way to deal with the flow of risk in that network. (For example, what if I3 and I5 happen at the same time? Do their opposite effects cancel out?)


Which type of graph theoretic representation is best suited for this problem? Note the added complication that the belief propagation doesn't flow "smoothly" through the nodes since, as we saw above, each node runs it's own inference based on it's intrinsic data. At each node, one should therefore merge the inference from the neighboring nodes as well as the inference from the intrinsic data of the node.

  • 1
    $\begingroup$ There are more general graphical models that allow cycles. See cs.ubc.ca/~murphyk/MLbook/pml-print3-ch19.pdf and cs.cmu.edu/~epxing/Class/10708-17/notes-17/… and cs.toronto.edu/~urtasun/courses/GraphicalModels/lecture5.pdf $\endgroup$ – Aryeh Nov 26 '18 at 18:22
  • $\begingroup$ @Aryeh I have a cursory high-level understanding of these models, but it's not clear to me that any of them account for the fact that the nodes themselves, independently of their interactions with neighboring nodes, generate their own belief scores based on machine learning. So the flow of belief isn't as seamless as in the textbook examples. Does that make sense or can one think of this differently? $\endgroup$ – Tfovid Nov 27 '18 at 10:12
  • $\begingroup$ You can have a potential that depends on the entire clique, including the states attached to the nodes. $\endgroup$ – Aryeh Nov 27 '18 at 10:22
  • $\begingroup$ @Aryeh Could you please expand on that? I still find it hard to see how could one reconcile a graph theoretic model based on some kind of probability propagation with a machine learning-driven model that generates probabilities at the nodes themselves. $\endgroup$ – Tfovid Dec 10 '18 at 14:31
  • $\begingroup$ Have you looked at the nodes I linked? In particular, the Hammersley–Clifford theorem en.wikipedia.org/wiki/Hammersley%E2%80%93Clifford_theorem ? $\endgroup$ – Aryeh Dec 10 '18 at 14:41

Your Answer

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

Browse other questions tagged or ask your own question.