Leiden algorithm - Revision history

Frap: /* Partition Quality */ MOS:HEAD

2025-05-15T22:14:09Z

Partition Quality: MOS:HEAD

← Previous revision		Revision as of 22:14, 15 May 2025
Line 77:		Line 77:


	==Partition ~~Quality~~==		==Partition quality==
	How communities are partitioned is an integral part on the Leiden algorithm. How partitions are decided can depend on how their quality is measured. Additionally, many of these metrics contain parameters of their own that can change the outcome of their communities.		How communities are partitioned is an integral part on the Leiden algorithm. How partitions are decided can depend on how their quality is measured. Additionally, many of these metrics contain parameters of their own that can change the outcome of their communities.

Line 132:		Line 132:
	Typically Potts models such as RB or CPM include a resolution parameter in their calculation.<ref name=":0" /><ref name="CPM" /> Potts models are introduced as a response to the resolution limit problem that is present in modularity maximization based community detection. The resolution limit problem is that, for some graphs, maximizing modularity may cause substructures of a graph to merge and become a single community and thus smaller structures are lost.<ref>{{Cite journal \|last=Fortunato \|first=Santo \|last2=Barthélemy \|first2=Marc \|date=2007-01-02 \|title=Resolution limit in community detection \|url=https://pnas.org/doi/full/10.1073/pnas.0605965104 \|journal=Proceedings of the National Academy of Sciences \|language=en \|volume=104 \|issue=1 \|pages=36–41 \|doi=10.1073/pnas.0605965104 \|issn=0027-8424 \|pmc=1765466 \|pmid=17190818}}</ref> These resolution parameters allow modularity adjacent methods to be modified to suit the requirements of the user applying the Leiden algorithm to account for small substructures at a certain granularity.		Typically Potts models such as RB or CPM include a resolution parameter in their calculation.<ref name=":0" /><ref name="CPM" /> Potts models are introduced as a response to the resolution limit problem that is present in modularity maximization based community detection. The resolution limit problem is that, for some graphs, maximizing modularity may cause substructures of a graph to merge and become a single community and thus smaller structures are lost.<ref>{{Cite journal \|last=Fortunato \|first=Santo \|last2=Barthélemy \|first2=Marc \|date=2007-01-02 \|title=Resolution limit in community detection \|url=https://pnas.org/doi/full/10.1073/pnas.0605965104 \|journal=Proceedings of the National Academy of Sciences \|language=en \|volume=104 \|issue=1 \|pages=36–41 \|doi=10.1073/pnas.0605965104 \|issn=0027-8424 \|pmc=1765466 \|pmid=17190818}}</ref> These resolution parameters allow modularity adjacent methods to be modified to suit the requirements of the user applying the Leiden algorithm to account for small substructures at a certain granularity.

	The figure on the right illustrates why resolution can be a helpful parameter when using modularity based quality metrics. In the first graph, modularity only captures the large scale structures of the graph; however, in the second example, a more granular quality metric could potentially detect all substructures in a graph.		The figure on the right illustrates why resolution can be a helpful parameter when using modularity based quality metrics. In the first graph, modularity only captures the large scale structures of the graph; however, in the second example, a more granular quality metric could potentially detect all substructures in a graph.

	==Algorithm==		==Algorithm==

Arjayay: Sp

2025-02-26T22:09:36Z

← Previous revision		Revision as of 22:09, 26 February 2025
Line 202:		Line 202:
	function refine_partition_subset(Graph G, Partition P, Subset S)		function refine_partition_subset(Graph G, Partition P, Subset S)
	R = {v \| v ∈ S, E(v, S − v) ≥ γ * degree(v) * (degree(S) − degree(v))}		R = {v \| v ∈ S, E(v, S − v) ≥ γ * degree(v) * (degree(S) − degree(v))}
	/* For node v, which is a member of subset S, check if E(v, S-v) (the edges of v connected to other members of the community S, excluding v itself) are above a certain scaling factor. degree(v) is the degree of node v and degree(S) is the total degree of the nodes in the subset S. This statement essentially requires that if v is removed from the subset, the community will remain ~~in tact~~. */		/* For node v, which is a member of subset S, check if E(v, S-v) (the edges of v connected to other members of the community S, excluding v itself) are above a certain scaling factor. degree(v) is the degree of node v and degree(S) is the total degree of the nodes in the subset S. This statement essentially requires that if v is removed from the subset, the community will remain intact. */
	for v ∈ R		for v ∈ R
	if v in singleton_community /* If node v is in a singleton community, meaning it is the only node. */		if v in singleton_community /* If node v is in a singleton community, meaning it is the only node. */

Beland: convert special characters found by Wikipedia:Typo Team/moss (via WP:JWB)

2025-02-11T02:43:35Z

convert special characters found by Wikipedia:Typo Team/moss (via WP:JWB)

← Previous revision		Revision as of 02:43, 11 February 2025
Line 207:		Line 207:
	T = {C \| C ∈ P, C ⊆ S, E(C, S − C) ≥ γ * degree(C) · (degree(S) − degree(C)}		T = {C \| C ∈ P, C ⊆ S, E(C, S − C) ≥ γ * degree(C) · (degree(S) − degree(C)}
	/* Create a set T of communities where E(C, S - C) (the edges between community C and subset S, excluding edges between community C and itself) is greater than the threshold. The threshold here is γ * degree(C) · (degree(S) − degree(C). */		/* Create a set T of communities where E(C, S - C) (the edges between community C and subset S, excluding edges between community C and itself) is greater than the threshold. The threshold here is γ * degree(C) · (degree(S) − degree(C). */
	Pr(C_prime = C) ∼ exp(1/θ ∆HP(v → C) if ∆HP(v → C) ≥ 0		Pr(C_prime = C) ~ exp(1/θ ∆HP(v → C) if ∆HP(v → C) ≥ 0
	0 otherwise for C ∈ T		0 otherwise for C ∈ T
	/* If moving the node v to C_prime changes the quality function in the positive direction, set the probability that the community of v to exp(1/θ * ∆HP(v → C)) else set it to 0 for all of the communities in T. */		/* If moving the node v to C_prime changes the quality function in the positive direction, set the probability that the community of v to exp(1/θ * ∆HP(v → C)) else set it to 0 for all of the communities in T. */

S2OP: Add a section giving a specific example which shows advantages over the Louvain method in community detection for certain types of graphs

2024-12-05T03:33:48Z

Add a section giving a specific example which shows advantages over the Louvain method in community detection for certain types of graphs

@@ Line 7: / Line 7: @@
 [[Louvain method]]. Like the Louvain method, the Leiden algorithm attempts to optimize [[Modularity (networks)|modularity]] in extracting communities from networks; however, it addresses key issues present in the Louvain method, namely poorly connected communities and the [[Modularity (networks)#Resolution limit|resolution limit of modularity]].
-Broadly, the Leiden algorithm uses the same two primary phases as the Louvain algorithm, a local node moving step (though, the method by which nodes are considered in Leiden is more efficient<ref name="Leiden" />) and a graph aggregation step. However, to address the issues with poorly connected communities and the merging of smaller communities into larger communities (the resolution limit of modularity), the Leiden algorithm employs an intermediate refinement phase in which communities may be split to guarantee that all communities are well-connected.
+Broadly, the Leiden algorithm uses the same two primary phases as the Louvain algorithm: a local node moving step (though, the method by which nodes are considered in Leiden is more efficient<ref name="Leiden" />) and a graph aggregation step. However, to address the issues with poorly-connected communities and the merging of smaller communities into larger communities (the resolution limit of modularity), the Leiden algorithm employs an intermediate refinement phase in which communities may be split to guarantee that all communities are well-connected.
 ==Graph components==

Enorby: Added a few sentences to better tie the images into the descriptions of each step

2024-12-04T19:54:01Z

Added a few sentences to better tie the images into the descriptions of each step

← Previous revision		Revision as of 19:54, 4 December 2024
Line 154:		Line 154:
	'''Step 1: Local Moving of Nodes'''		'''Step 1: Local Moving of Nodes'''

	First, we move the nodes from <math>\mathcal{P}</math> into neighboring communities to maximize [[Modularity (networks) \| modularity]] (the difference in quality between the generated partition and a hypothetical randomized partition of communities).		First, we move the nodes from <math>\mathcal{P}</math> into neighboring communities to maximize [[Modularity (networks) \| modularity]] (the difference in quality between the generated partition and a hypothetical randomized partition of communities). In the above image, our initial collection of unsorted nodes is represented by the graph on the left, with each node's unique color representing that they do not belong to a community yet. The graph on the right is a representation of this step's result, the sorted graph <math>\mathcal{P}</math>; note how the nodes have all been moved into one of three communities, as represented by the nodes' colors (red, blue, and green).

	<pre>function fast_louvain_move_nodes(Graph G, Partition P)		<pre>function fast_louvain_move_nodes(Graph G, Partition P)
Line 175:		Line 175:
	'''Step 2: Refinement of the Partition'''		'''Step 2: Refinement of the Partition'''

	Next, each node in the network is assigned to its own individual community and then moved them from one community to another to maximize modularity. This occurs iteratively until each node has been visited and moved, and each community ~~has been~~ refined. ~~This~~ ~~forms~~ our initial partition for <math>\mathcal{P}_{\text{refined}}</math>.		Next, each node in the network is assigned to its own individual community and then moved them from one community to another to maximize modularity. This occurs iteratively until each node has been visited and moved, and is very similar to the creation of <math>\mathcal{P}</math> except that each community is refined after a node is moved. The result is our initial partition for <math>\mathcal{P}_{\text{refined}}</math>, as shown on the right. Note that we're also keeping track of the communities from <math>\mathcal{P}</math>, which are represented by the colored backgrounds behind the nodes.

	<pre>		<pre>
Line 207:		Line 207:
	'''Step 3: Aggregation of the Network'''		'''Step 3: Aggregation of the Network'''

	We then convert each community in <math>\mathcal{P}_{\text{refined}}</math> into a single node.		We then convert each community in <math>\mathcal{P}_{\text{refined}}</math> into a single node. Note how, as is depicted in the above image, the communities of <math>\mathcal{P}</math> are used to sort these aggregate nodes after their creation.

	<pre>function aggregate_graph(Graph G, Partition P)		<pre>function aggregate_graph(Graph G, Partition P)

161.106.4.5: Correct arxiv link of reference: ``GVE-Leiden: Fast Leiden Algorithm for Community Detection in Shared Memory Setting''

2024-12-02T10:59:17Z

Correct arxiv link of reference: ``GVE-Leiden: Fast Leiden Algorithm for Community Detection in Shared Memory Setting''

← Previous revision		Revision as of 10:59, 2 December 2024
Line 225:		Line 225:
	The Leiden algorithm does a great job of creating a quality partition which places nodes into distinct communities. However, Leiden creates a hard partition, meaning nodes can belong to only one community. In many networks such as social networks, nodes may belong to multiple communities and in this case other methods may be preferred.		The Leiden algorithm does a great job of creating a quality partition which places nodes into distinct communities. However, Leiden creates a hard partition, meaning nodes can belong to only one community. In many networks such as social networks, nodes may belong to multiple communities and in this case other methods may be preferred.

	Leiden is more efficient than Louvain, but in the case of massive graphs may result in extended processing times. Recent advancements have boosted the speed using a "parallel multicore implementation of the Leiden algorithm".<ref>{{cite arxiv \|eprint=~~2311~~.~~05420~~ \|first1=Zizhang \|last1=Yang \|first2=Junhao \|last2=Wang \|title=GVE-Leiden: Fast Leiden Algorithm for Community Detection in Shared Memory Setting \|date=2023}}</ref>		Leiden is more efficient than Louvain, but in the case of massive graphs may result in extended processing times. Recent advancements have boosted the speed using a "parallel multicore implementation of the Leiden algorithm".<ref>{{cite arxiv \|eprint=2312.13936 \|first1=Zizhang \|last1=Yang \|first2=Junhao \|last2=Wang \|title=GVE-Leiden: Fast Leiden Algorithm for Community Detection in Shared Memory Setting \|date=2023}}</ref>

	The Leiden algorithm does much to overcome the resolution limit problem. However, there is still the possibility that small substructures can be missed in certain cases. The selection of the gamma parameter is crucial to ensure that these structures are not missed, as it can vary significantly from one graph to the next.		The Leiden algorithm does much to overcome the resolution limit problem. However, there is still the possibility that small substructures can be missed in certain cases. The selection of the gamma parameter is crucial to ensure that these structures are not missed, as it can vary significantly from one graph to the next.

WikiCleanerBot: v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

2024-11-28T04:58:10Z

v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

← Previous revision		Revision as of 04:58, 28 November 2024
Line 116:		Line 116:
	=== Understanding Potts Model resolution parameters/Resolution limit ===		=== Understanding Potts Model resolution parameters/Resolution limit ===
	[[File:Modularity vs substructure.png\|thumb\|183x183px\|The image depicts 2 separate community interpretations of the graph shown. The first graph shows 2 separate communities(1 blue, 1 red) that attempt to maximize modularity. The second graph interpretation shows 3 communities(1 blue, 1 red, 1 green) that show a more accurate representation of the substructures within the graph]]		[[File:Modularity vs substructure.png\|thumb\|183x183px\|The image depicts 2 separate community interpretations of the graph shown. The first graph shows 2 separate communities(1 blue, 1 red) that attempt to maximize modularity. The second graph interpretation shows 3 communities(1 blue, 1 red, 1 green) that show a more accurate representation of the substructures within the graph]]
	Typically Potts models such as RB or CPM include a resolution parameter in their calculation<ref name=":0" /><ref name="CPM" />. Potts models are introduced as a response to the resolution limit problem that is present in modularity maximization based community detection. The resolution limit problem is that, for some graphs, maximizing modularity may cause substructures of a graph to merge and become a single community and thus smaller structures are lost.<ref>{{Cite journal \|last=Fortunato \|first=Santo \|last2=Barthélemy \|first2=Marc \|date=2007-01-02 \|title=Resolution limit in community detection \|url=https://pnas.org/doi/full/10.1073/pnas.0605965104 \|journal=Proceedings of the National Academy of Sciences \|language=en \|volume=104 \|issue=1 \|pages=36–41 \|doi=10.1073/pnas.0605965104 \|issn=0027-8424 \|pmc=1765466 \|pmid=17190818}}</ref> These resolution parameters allow modularity adjacent methods to be modified to suit the requirements of the user applying the Leiden algorithm to account for small substructures at a certain granularity.		Typically Potts models such as RB or CPM include a resolution parameter in their calculation.<ref name=":0" /><ref name="CPM" /> Potts models are introduced as a response to the resolution limit problem that is present in modularity maximization based community detection. The resolution limit problem is that, for some graphs, maximizing modularity may cause substructures of a graph to merge and become a single community and thus smaller structures are lost.<ref>{{Cite journal \|last=Fortunato \|first=Santo \|last2=Barthélemy \|first2=Marc \|date=2007-01-02 \|title=Resolution limit in community detection \|url=https://pnas.org/doi/full/10.1073/pnas.0605965104 \|journal=Proceedings of the National Academy of Sciences \|language=en \|volume=104 \|issue=1 \|pages=36–41 \|doi=10.1073/pnas.0605965104 \|issn=0027-8424 \|pmc=1765466 \|pmid=17190818}}</ref> These resolution parameters allow modularity adjacent methods to be modified to suit the requirements of the user applying the Leiden algorithm to account for small substructures at a certain granularity.

	The figure on the right illustrates why resolution can be a helpful parameter when using modularity based quality metrics. In the first graph, modularity only captures the large scale structures of the graph; however, in the second example, a more granular quality metric could potentially detect all substructures in a graph.		The figure on the right illustrates why resolution can be a helpful parameter when using modularity based quality metrics. In the first graph, modularity only captures the large scale structures of the graph; however, in the second example, a more granular quality metric could potentially detect all substructures in a graph.
Line 225:		Line 225:
	The Leiden algorithm does a great job of creating a quality partition which places nodes into distinct communities. However, Leiden creates a hard partition, meaning nodes can belong to only one community. In many networks such as social networks, nodes may belong to multiple communities and in this case other methods may be preferred.		The Leiden algorithm does a great job of creating a quality partition which places nodes into distinct communities. However, Leiden creates a hard partition, meaning nodes can belong to only one community. In many networks such as social networks, nodes may belong to multiple communities and in this case other methods may be preferred.

	Leiden is more efficient than Louvain, but in the case of massive graphs may result in extended processing times. Recent advancements have boosted the speed using a "parallel multicore implementation of the Leiden algorithm"<ref>{{cite arxiv \|eprint=2311.05420 \|first1=Zizhang \|last1=Yang \|first2=Junhao \|last2=Wang \|title=GVE-Leiden: Fast Leiden Algorithm for Community Detection in Shared Memory Setting \|date=2023}}</ref>.		Leiden is more efficient than Louvain, but in the case of massive graphs may result in extended processing times. Recent advancements have boosted the speed using a "parallel multicore implementation of the Leiden algorithm".<ref>{{cite arxiv \|eprint=2311.05420 \|first1=Zizhang \|last1=Yang \|first2=Junhao \|last2=Wang \|title=GVE-Leiden: Fast Leiden Algorithm for Community Detection in Shared Memory Setting \|date=2023}}</ref>

	The Leiden algorithm does much to overcome the resolution limit problem. However, there is still the possibility that small substructures can be missed in certain cases. The selection of the gamma parameter is crucial to ensure that these structures are not missed, as it can vary significantly from one graph to the next.		The Leiden algorithm does much to overcome the resolution limit problem. However, there is still the possibility that small substructures can be missed in certain cases. The selection of the gamma parameter is crucial to ensure that these structures are not missed, as it can vary significantly from one graph to the next.

Dee Xen: I added a limitations section, discussing a few ways in which Leiden can be insufficient according to what is needed for community detection.

2024-11-26T19:13:06Z

I added a limitations section, discussing a few ways in which Leiden can be insufficient according to what is needed for community detection.

← Previous revision		Revision as of 19:13, 26 November 2024
Line 221:		Line 221:

	We repeat these steps until each community contains only one node, with each of these nodes representing an aggregate of nodes from the original network that are strongly connected with each other.		We repeat these steps until each community contains only one node, with each of these nodes representing an aggregate of nodes from the original network that are strongly connected with each other.

			==Limitations==
			The Leiden algorithm does a great job of creating a quality partition which places nodes into distinct communities. However, Leiden creates a hard partition, meaning nodes can belong to only one community. In many networks such as social networks, nodes may belong to multiple communities and in this case other methods may be preferred.

			Leiden is more efficient than Louvain, but in the case of massive graphs may result in extended processing times. Recent advancements have boosted the speed using a "parallel multicore implementation of the Leiden algorithm"<ref>{{cite arxiv \|eprint=2311.05420 \|first1=Zizhang \|last1=Yang \|first2=Junhao \|last2=Wang \|title=GVE-Leiden: Fast Leiden Algorithm for Community Detection in Shared Memory Setting \|date=2023}}</ref>.

			The Leiden algorithm does much to overcome the resolution limit problem. However, there is still the possibility that small substructures can be missed in certain cases. The selection of the gamma parameter is crucial to ensure that these structures are not missed, as it can vary significantly from one graph to the next.

	==References==		==References==

OAbot: Open access bot: arxiv updated in citation with #oabot.

2024-11-25T04:12:53Z

Open access bot: arxiv updated in citation with #oabot.

← Previous revision		Revision as of 04:12, 25 November 2024
Line 101:		Line 101:

	===Reichardt Bornholdt Potts Model (RB)===		===Reichardt Bornholdt Potts Model (RB)===
	One of the most well used metrics for the Leiden algorithm is the Reichardt Bornholdt Potts Model (RB).<ref name=":0">{{Cite journal \|last=Reichardt \|first=Jörg \|last2=Bornholdt \|first2=Stefan \|date=2004-11-15 \|title=Detecting Fuzzy Community Structures in Complex Networks with a Potts Model \|url=https://link.aps.org/doi/10.1103/PhysRevLett.93.218701 \|journal=Physical Review Letters \|language=en \|volume=93 \|issue=21 \|doi=10.1103/PhysRevLett.93.218701 \|issn=0031-9007}}</ref> This model is used by default in most mainstream Leiden algorithm libraries under the name '''RBConfigurationVertexPartition'''.<ref name="leidenalg">{{Cite web \|title=Reference — leidenalg 0.10.3.dev0+gcb0bc63.d20240122 documentation \|url=https://leidenalg.readthedocs.io/en/stable/reference.html \|access-date=2024-11-23 \|website=leidenalg.readthedocs.io \|language=en}}</ref><ref name="leidenR">https://cran.r-project.org/web/packages/leiden/leiden.pdf</ref> This model introduces a resolution parameter <math>\gamma</math> and is highly similar to the equation for modularity. This model is defined by the following quality function for an adjacency matrix, A, as:<ref name="leidenalg"></ref>		One of the most well used metrics for the Leiden algorithm is the Reichardt Bornholdt Potts Model (RB).<ref name=":0">{{Cite journal \|last=Reichardt \|first=Jörg \|last2=Bornholdt \|first2=Stefan \|date=2004-11-15 \|title=Detecting Fuzzy Community Structures in Complex Networks with a Potts Model \|url=https://link.aps.org/doi/10.1103/PhysRevLett.93.218701 \|journal=Physical Review Letters \|language=en \|volume=93 \|issue=21 \|doi=10.1103/PhysRevLett.93.218701 \|issn=0031-9007\|arxiv=cond-mat/0402349 }}</ref> This model is used by default in most mainstream Leiden algorithm libraries under the name '''RBConfigurationVertexPartition'''.<ref name="leidenalg">{{Cite web \|title=Reference — leidenalg 0.10.3.dev0+gcb0bc63.d20240122 documentation \|url=https://leidenalg.readthedocs.io/en/stable/reference.html \|access-date=2024-11-23 \|website=leidenalg.readthedocs.io \|language=en}}</ref><ref name="leidenR">https://cran.r-project.org/web/packages/leiden/leiden.pdf</ref> This model introduces a resolution parameter <math>\gamma</math> and is highly similar to the equation for modularity. This model is defined by the following quality function for an adjacency matrix, A, as:<ref name="leidenalg"></ref>

	<math>Q=\sum_{ij}(A_{ij}-\gamma\frac{k_ik_j}{2m})\delta(c_i, c_j)</math>		<math>Q=\sum_{ij}(A_{ij}-\gamma\frac{k_ik_j}{2m})\delta(c_i, c_j)</math>

Dee Xen: Cleaned up comments for multiline.

2024-11-23T15:30:23Z

Cleaned up comments for multiline.

Show changes