# Graph algorithm or framework for determining node affinity based on utilities

I'm looking for an algorithm or framework for thinking about how to determine affinities between nodes. Perhaps affinity is poor choice of wording, but basically I want to use utilities between nodes to determine how alike or unalike they are from each other. I've attached an example diagram to illustrate what I mean:

In this example, Entities A and B are not well-aligned due to the negative utility between them. An appropriate algorithm or framework should identify that they belong to different groups, clusters, etc.

Additionally, I should be able to infer that Entities B and C are likely to be well-aligned, due to the mutual misalignment with A.

The utility magnitudes should also reflect the degree of alignment or misalignment. For example A2 and B3 should more more misaligned than A1 and B3.

To complicate things further, the utility "units" may be different, with multiple edges between nodes. As a simplifying assumption, I may be able to normalize utilities into a single edge and unit.

I apologize if this question is vague and/or ill-suited for this StackExchange. However I really don't have a good lead on how to tackle such a problem.

• What are A1, B1 etc.? What the edge units represent? Are you sure that double misalignment is good indicator of mutual alignment? I see 4 steps between Entity B and C and cannot say what is the difference between Entity A <-> Entity B edge (-10) and say Entity A and A1 (are these different in any way?). " A2 and B3 should more more misaligned than A2 and B3." That may be hard, probably a spelling mistake. If you may normalise the edges, does this operation induce some errors? If not, could you present the easiest form of the task? Could you do topological sorting (I bet not, but then, why?) – Evil Feb 10 '18 at 1:20
• Hi @Evil, the A1, B1, etc. were meant to be smaller entities aligned with their respective larger entity. I wanted to show that alignment information should flow between them as well. Double misalignment may not be a good indicator; perhaps I could project entities onto idealized entities as in Latent Semantic Analysis, if there's an analogous method for graphs. The -10 edge indicates a strong negative/harmful relationship, while the +1 weight indicates a small positive/beneficial relationship. That was a typo, fixed it. I'd say this is the simplest form I could think of, edges already norm'd. – trianta2 Feb 10 '18 at 5:01
• Thank you. "For example A2 and B3 should more more misaligned than A2 and B3." is still in your question. What is the difference between smaller and bigger entity? – Evil Feb 10 '18 at 10:43
• Whoops, the typo is definitely fixed now. In hindsight, perhaps it was confusing to mention bigger entities initially. What I wanted to communicate was that there are "big players" that mostly interact with each other, and "small players" that mainly act as supports for the big entities, and may not have direct edges to other smaller entities. In other words, there is a hierarchical structure with big and small entities. – trianta2 Feb 10 '18 at 22:41