<p>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.</p>

<p><strong>BACKGROUND EXAMPLE</strong></p>

<p>Consider the following individuals forming nodes in the larger network of society.</p>

<p>John:</p>

<ul>
<li>62 years old, clean criminal record</li>
<li>married and father of two</li>
<li>works as a psychologist</li>
<li>pays his taxes</li>
<li>gives to charity</li>
</ul>

<p>Ted:</p>

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

<p>Robert:</p>

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

<p>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 <code>John = 0</code>, <code>Ted = 1</code>, and <code>Robert = 2</code>.</p>

<p>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 (<code>Ix</code>) could be:</p>

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

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

<ul>
<li><code>I1</code>: Ted's risk goes up. Robert's risk stays the same.</li>
<li><code>I2</code>: John's and Ted's risks stay the same.</li>
<li><code>I3</code>: Robert's risk goes down. John's risk stays the same.</li>
<li><code>I4</code>: Robert's risk goes down. Ted's risk stays the same.</li>
<li><code>I5</code>: John's risk goes up. Roberts's risk stays the same.</li>
</ul>

<p>It's therefore clear that the <em>direction</em> and <em>nature</em> of the interaction matters in inferring the risk scores. Any graph that represents these interactions should also allow for <em>cycles</em>, 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 <code>I3</code> and <code>I5</code> happen at the same time? Do their opposite effects cancel out?)</p>

<p><strong>QUESTION</strong></p>

<p>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.</p>

CC BY-SA 4.0
2018-11-26T18:22:27.570Z
There are more general graphical models that allow cycles. See https://www.cs.ubc.ca/~murphyk/MLbook/pml-print3-ch19.pdf
and
https://www.cs.cmu.edu/~epxing/Class/10708-17/notes-17/10708-scribe-lecture3.pdf
and
https://www.cs.toronto.edu/~urtasun/courses/GraphicalModels/lecture5.pdf
Aryeh
CC BY-SA 4.0
2018-11-27T10:12:41.157Z
@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?
Tfovid
CC BY-SA 4.0
2018-11-27T10:22:49.647Z
You can have a potential that depends on the entire clique, including the states attached to the nodes.
Aryeh
CC BY-SA 4.0
2018-12-10T14:31:10.050Z
@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.
Tfovid
CC BY-SA 4.0
2018-12-10T14:41:54.597Z
Have you looked at the nodes I linked? In particular, the Hammersley–Clifford theorem https://en.wikipedia.org/wiki/Hammersley%E2%80%93Clifford_theorem ?
Aryeh
<graph-theory><graph-algorithms><machine-learning><directed-acyclic-graph><markov-chains>
Crime prevention using graph theory and machine learning
Tfovid
# Crime prevention using graph theory and machine learning

(Asked by: username_0 on 2018-11-26)

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.

**BACKGROUND EXAMPLE**

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

John:

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

Ted:

* 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

Robert:

* 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?)

**QUESTION**

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.

**Tags:** graph-theory, graph-algorithms, machine-learning, directed-acyclic-graph, markov-chains
> **Comments:**
> **username_1**: There are more general graphical models that allow cycles. See https://www.cs.ubc.ca/~murphyk/MLbook/pml-print3-ch19.pdf and https://www.cs.cmu.edu/~epxing/Class/10708-17/notes-17/10708-scribe-lecture3.pdf and https://www.cs.toronto.edu/~urtasun/courses/GraphicalModels/lecture5.pdf  
> **username_0**: @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?  
> **username_1**: You can have a potential that depends on the entire clique, including the states attached to the nodes.  
> **username_0**: @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.  
> **username_1**: Have you looked at the nodes I linked? In particular, the Hammersley–Clifford theorem https://en.wikipedia.org/wiki/Hammersley%E2%80%93Clifford_theorem ?  

---

## 0 answers

