Editing Line graph (section)

===Weighted line graphs===
In a line graph {{math|''L''(''G'')}}, each vertex of degree {{mvar|k}} in the original graph {{mvar|G}} creates {{math|''k''(''k'' − 1)/2}} edges in the line graph.  For many types of analysis this means high-degree nodes in {{mvar|G}} are over-represented in the line graph {{math|''L''(''G'')}}.  For instance, consider a [[random walk]] on the vertices of the original graph {{mvar|G}}.  This will pass along some edge {{mvar|e}} with some frequency {{mvar|f}}. On the other hand, this edge {{mvar|e}} is mapped to a unique vertex, say {{mvar|v}}, in the line graph {{math|''L''(''G'')}}.  If we now perform the same type of random walk on the vertices of the line graph, the frequency with which {{mvar|v}} is visited can be completely different from ''f''.  If our edge {{mvar|e}} in {{mvar|G}} was connected to nodes of degree {{math|''O''(''k'')}}, it will be traversed {{math|''O''(''k''{{sup|2}})}} more frequently in the line graph {{math|''L''(''G'')}}.  Put another way, the Whitney graph isomorphism theorem guarantees that the line graph almost always encodes the topology of the original graph {{mvar|G}} faithfully but it does not guarantee that dynamics on these two graphs have a simple relationship.  One solution is to construct a weighted line graph, that is, a line graph with [[Weighted graph|weighted edges]].  There are several natural ways to do this.{{sfnp|Evans|Lambiotte|2009}} For instance if edges {{mvar|d}} and {{mvar|e}} in the graph {{mvar|G}} are incident at a vertex {{mvar|v}} with degree {{mvar|k}}, then in the line graph {{math|''L''(''G'')}} the edge connecting the two vertices {{mvar|d}} and {{mvar|e}} can be given weight {{math|1/(''k'' − 1)}}.  In this way every edge in {{mvar|G}} (provided neither end is connected to a vertex of degree 1) will have strength 2 in the line graph {{math|''L''(''G'')}} corresponding to the two ends that the edge has in {{mvar|G}}. It is straightforward to extend this definition of a weighted line graph to cases where the original graph {{mvar|G}} was directed or even weighted.{{sfnp|Evans|Lambiotte|2010}}  The principle in all cases is to ensure the line graph {{math|''L''(''G'')}} reflects the dynamics as well as the topology of the original graph {{mvar|G}}.