💻 computer science

Partitioning Israeli Municipalities into Politically Homogeneous Cantons: A Constrained Spatial Clustering Approach

This paper presents a data-driven algorithmic framework that partitions 229 Israeli municipalities into geographically contiguous, politically homogeneous cantons, demonstrating that despite recent electoral volatility, Israel's underlying political geography remains structurally consistent and can be effectively modeled using constrained spatial clustering techniques.

Original authors: Adir Elmakais, Oren Glickman

Published 2026-03-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Adir Elmakais, Oren Glickman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, messy box of LEGO bricks. Each brick represents a town in Israel. Some bricks are red, some blue, some yellow, and some are a mix of colors. In recent years, the people living in these towns have voted in very different ways, creating a lot of political tension.

Some people have joked, "What if we just split the country up into separate neighborhoods where everyone thinks the same way?" This paper asks: If we actually tried to do that using math, what would the map look like?

Here is the story of how the authors tried to solve this puzzle.

1. The Goal: Sorting the LEGO Box

The authors wanted to take all 229 towns in Israel and group them into "cantons" (like separate rooms in a house). They had three strict rules for sorting:

Same Room, Same Vibe: Everyone in a room must vote very similarly (political homogeneity).
No Floating Islands: The towns in a room must be physically touching each other on the map. You can't have a room that includes a town in the north and a town in the south with a gap in between.
Fair Room Sizes: Try to keep the number of people in each room roughly equal (though this was a secondary goal).

2. The Tools: Four Different Sorters

To figure out the best way to group these towns, the researchers built four different "robot sorters" (algorithms) and tested them against each other. They also tried looking at the voting data in four different ways (like looking at the LEGO bricks from different angles).

The "Glue" Sorter (Agglomerative): This one starts with every town as its own tiny group and slowly glues the most similar neighbors together. It's great at finding perfect matches, but sometimes it makes rooms that are way too big or too small.
The "Optimizer" Sorter (Simulated Annealing): This one is like a chef tasting a soup. It tries a mix, tastes it, and if it's too salty (too unbalanced), it tweaks the recipe. It tries thousands of random combinations to find the perfect balance, but it's slow and sometimes gets stuck.
The "Social Network" Sorter (Louvain): This one looks at the towns like a social network. It asks, "Who hangs out with whom?" and naturally forms groups based on who is closest. It's very fast and surprisingly stable.
The "Standard" Sorter (K-Means): This is the basic, no-frills sorter. It ignores geography completely. It might put a town in the north in the same room as a town in the south just because they voted the same way. (The authors used this just to see how bad it would be).

3. The Experiment: 264 Different Ways to Slice the Pie

The researchers didn't just run the test once. They ran it 264 times, mixing and matching:

Different ways to measure "similarity" (e.g., just looking at the main political blocs vs. looking at every single party).
Different numbers of rooms (3 rooms, 5 rooms, 10 rooms, etc.).

4. The Big Discovery: The "Five-Region" Map

After running all the tests, they found that splitting Israel into 5 regions using the "Social Network" sorter (Louvain) made the most sense.

Here is what those 5 "rooms" looked like:

The Center Metro: A big, secular, center-leaning bubble around Tel Aviv.
The Right-Wing South: A long, connected arc of towns stretching from Jerusalem down through the desert to Eilat. These towns lean heavily to the right.
The Right-Wing North: A mixed bag in the north, including Haifa and Jewish towns in the Galilee.
The Arab Galilee: A distinct cluster of Arab-majority towns in the north.
The Arab Periphery: Another distinct cluster of Arab-majority towns (mostly Bedouin) in the south.

The Analogy: Imagine a party where people are mingling. Even though everyone is in the same building, if you look closely, you see that the secular people are huddled near the DJ, the religious people are near the food table, and the Arab communities are chatting in their own distinct corners. The math just drew lines around those natural clusters.

5. The "Time Travel" Test

The researchers checked if these groups would stay the same if they used election results from different years (2019, 2020, 2021, 2022).

The Result: The groups were rock solid. Even though the specific votes changed a little bit from year to year, the "rooms" didn't change. The map of who votes like whom is deeply rooted in the geography. It's not a fluke; it's a structural feature of Israeli society.

6. What This Means (and What It Doesn't)

It's not a political proposal: The authors are not saying Israel should be split up. They are just saying, "If we did split it up based purely on voting patterns, this is what the map would look like."
It reveals the divide: The map clearly shows that the biggest split isn't just "Left vs. Right," but also "Jewish vs. Arab." The Arab towns naturally form their own separate, cohesive groups, distinct from the Jewish towns.
It's not about city limits: The political "rooms" don't match the official administrative districts. Politics follows the people's minds, not the government's map lines.

The Takeaway

This paper is like using a high-tech scanner to see the "skeleton" of a country's politics. It shows that despite all the noise and arguments in the news, the underlying structure of Israeli society is surprisingly stable and clearly divided into five distinct, geographically connected political tribes. The math confirms what many people feel: we live in very different worlds, even if we are neighbors.

1. Problem Definition

The paper addresses the Constrained Canton Partitioning Problem, a variant of the regionalization problem. The goal is to partition $n$ Israeli municipalities into $K$ geographically contiguous regions (cantons) that maximize internal political homogeneity while balancing population and maintaining geographic compactness.

Formal Constraints & Objectives:

Input: A set of municipalities $V$ , a geographic contiguity graph $G=(V, E)$ , political feature vectors $f_i$ derived from election results, and voter weights $w_i$ .
Objectives:
1. Maximize Homogeneity: Minimize within-canton political variance.
2. Ensure Contiguity: Each canton must form a connected subgraph of $G$ .
3. Balance Population: Minimize the disparity in total voter population across cantons.
Cost Function: A weighted multi-objective function:
$Cost(C) = \alpha \cdot Homogeneity(C) + \beta \cdot Balance(C) + \gamma \cdot Compactness(C)$
Where $\alpha=0.4, \beta=0.4, \gamma=0.2$ .

2. Methodology

Data Sources

Election Data: Municipality-level results from five consecutive Knesset elections (2019–2022) obtained from the Israel Central Bureau of Statistics (CBS).
Geographic Data: Municipal boundary polygons (Shapefiles) from CBS, processed into a connected graph of 229 municipalities.
Feature Engineering: Parties were mapped to five political blocs (Right, Haredi, Center, Left, Arab).

Feature Representations

Four distinct feature spaces were evaluated:

BlocShares: 11-dimensional vector (mean/std of vote shares for 5 blocs across 5 elections + avg voter count).
RawParty: High-dimensional vector of individual party vote shares.
PCA_5: 5 principal components derived from RawParty.
NMF_5: 5 non-negative components derived from Non-negative Matrix Factorization of RawParty (interpretable as political archetypes).

Algorithms

The study compared four clustering approaches:

Simulated Annealing (SA): A metaheuristic optimizing the multi-objective cost function. It uses a Metropolis criterion to accept moves that improve the cost or, with decreasing probability, moves that increase it, while strictly enforcing contiguity.
Agglomerative Clustering: Hierarchical clustering with average linkage and strict contiguity constraints (merging only adjacent clusters).
Louvain Community Detection: Maximizes modularity on a graph where edge weights are based on political similarity ( $1 - \text{distance}$ ). The resolution parameter is tuned via binary search to approximate a target $K$ .
K-Means (Baseline): Standard K-Means in feature space without geographic constraints (serves as a control for spatial effects).

Experimental Design

Grid Search: 264 experimental configurations (4 representations $\times$ 3 distance metrics $\times$ 4 algorithms $\times$ 6 values of $K$ ).
Distance Metrics: Euclidean, Cosine, and Jensen-Shannon (JS) distance.
Evaluation Metrics: Silhouette Score (clustering quality), Coefficient of Variation (population balance), and Adjusted Rand Index (temporal stability across elections).

3. Key Results

Clustering Quality vs. Constraints

Highest Silhouette: The Agglomerative algorithm using BlocShares features and Euclidean distance achieved the highest silhouette score (0.905) at $K=3$ . However, this resulted in severe population imbalance (CV = 1.13) and overly coarse regions.
Best Balance & Interpretability: The Louvain algorithm using NMF_5 features and Cosine distance at $K=5$ was selected as the primary result. While it had a lower silhouette score (0.121), it offered:
- Superior population balance (CV = 0.69).
- Perfect temporal stability (ARI = 1.0).
- Politically granular regions that distinguish between center-metropolitan and right-periphery Jewish communities.

Temporal Stability

Deterministic Stability: Algorithms like Louvain and Agglomerative produced near-perfectly stable partitions (ARI $\approx$ 0.95–1.0) across all five elections, indicating that Israel's political geography is structurally consistent despite electoral volatility.
Stochastic Variance: Simulated Annealing showed higher variance depending on the feature representation (NMF was most stable; PCA was least stable), suggesting that deterministic graph-based methods are more robust for this specific problem.

The $K=5$ Partition Structure

The optimal partition identified five distinct regions:

Center Metro: Secular, center-leaning core (Tel Aviv, Sharon plain).
Right South: Right-wing arc from Jerusalem through the Negev to Eilat.
Right North: Mixed northern region (Haifa, Galilee Jewish towns).
Arab Galilee: High cohesion Arab-majority towns in the north.
Arab Periphery: Bedouin towns in the Negev and scattered Arab municipalities.

4. Key Contributions

Novel Application: First application of constrained spatial clustering specifically to Israeli political geography, combining graph-based contiguity with political feature optimization.
Comprehensive Framework: A systematic evaluation of 264 configurations, providing a benchmark for how feature representation, distance metrics, and algorithms interact in political regionalization.
Stability Analysis: Demonstrated that Israel's political geography is structurally persistent across election cycles, with deterministic algorithms yielding identical partitions regardless of the specific election year used.
Qualitative Validation: Showed that algorithmic cantons align with known political-demographic cleavages (e.g., the Arab-Jewish divide, the secular-religious split) better than administrative districts (ARI = 0.435 between political cantons and official districts).
Open Resources: Provided an open-source Python codebase and an interactive web application for exploring the partitions.

5. Significance and Limitations

Significance:
The paper moves beyond rhetorical discussions of "dividing Israel" by providing a rigorous, data-driven methodology to visualize political polarization. It proves that political homogeneity can be achieved through contiguous geographic partitioning, revealing that the "periphery vote" and the "Arab-Jewish divide" are the dominant structural forces in Israeli politics, overriding administrative boundaries.

Limitations:

Ecological Fallacy: Analysis is at the municipality level; individual voter preferences within a municipality are aggregated and hidden.
Population Imbalance: The most homogeneous partitions (Agglomerative) often resulted in highly unequal population sizes.
Static Snapshot: The analysis treats elections as static snapshots without modeling long-term demographic shifts.
Selection Bias: With 264 configurations, the "best" results may be slightly inflated by selection effects, though relative rankings remain robust.

Conclusion

The study concludes that NMF_5 with Louvain Community Detection at $K=5$ offers the best trade-off between political coherence, population balance, and temporal stability. It confirms that Israel's political landscape is deeply polarized along spatial and demographic lines, forming five distinct, contiguous political regions that differ significantly from the country's official administrative districts.