Inferring households from call, location and subscription signals with Louvain community detection

LG Uplus sells mobile lines to individuals and internet, IPTV and bundles to homes. Understanding customers only as individuals misses the family and household-level patterns that matter for bundled products, targeting, retention and service recommendations: who should be offered a family plan, which home is one cancellation away from losing three lines. The obvious proxy, the billing account, splits families across accounts and carries lines that are not family at all. No single behavioural signal fixes that either — neighbours share a cell at night, colleagues call each other daily, and an account can carry an employee's line.

In this post we walk through the model we built instead. It turns call history, location information and subscription data into pairwise relationship evidence, combines that evidence into a weighted relationship graph, and treats families and households as small communities in it: Parallel Louvain community detection finds tightly connected groups, location-based inference turns groups into homes, and a head-of-household ID tracks each family as members join, leave and move. Along the way we explain why modularity optimization on its own merges small households, and how the live model below handles that with a strong-tie stage, bridge cuts and a size split.

Solution overview

The model works in two directions at once. Within a run, signals are aggregated per pair of lines, combined into edge weights and partitioned by community detection over the full subscriber graph, and homes are identified inside each community. Across runs, the result is reconciled with the previous one so that each household keeps its identifier, which is what other teams join their own data to.

The numbered steps in the diagram:

1. Call history, location information and subscription data, together with other variables that help tell family apart, are aggregated per pair of lines into relationship evidence.
2. The evidence is combined into one edge weight per pair of lines; no single signal is trusted on its own.
3. Parallel Louvain maximizes modularity over the full subscriber graph and returns tightly connected groups of lines.
4. Inside each group, location-based inference identifies the lines that share a home; the live model uses strong ties, bridge cuts and a size split instead.
5. Each household is anchored to a head of household, and its ID is carried forward when the next run finds the same household again.
6. The household ID becomes a dimension for segmentation, bundled-product strategy and family-level campaigns.

Technology stack

Step 1: Turn raw signals into pairwise evidence

Family relationships are not recorded anywhere, so they have to be inferred from behaviour. Three kinds of signal carried most of the information — call history between lines, location information and service-subscription data — together with other variables that help tell family apart. Each is aggregated to the pair of lines it describes over a fixed window, so that every later step works on one row per pair.

Each signal fails in its own way, which is why none is used alone:

• Calls separate family from strangers well, but close friends and colleagues can call just as often, and some family members hardly call each other.
• Night-time location is strong in low-rise areas, where a cell covers a few homes, and weak in apartment blocks, where it covers dozens.
• Shared accounts split families who pay separately and include lines that are not family, such as an employee's.

import pandas as pd

def unordered(df, a, b):
    """Canonical pair order, so (x, y) and (y, x) aggregate together."""
    return df.assign(i=df[[a, b]].min(axis=1), j=df[[a, b]].max(axis=1))

def pair_evidence(calls, nights, lines):
    """calls: (caller, callee) per call; nights: (line, night, area) per night;
    lines: (line, account). Returns one row of evidence per pair of lines."""
    c = unordered(calls, "caller", "callee").groupby(["i", "j"]).size()

    co = nights.merge(nights, on=["night", "area"])          # blocked by area
    co = unordered(co[co.line_x != co.line_y], "line_x", "line_y")
    n = co.groupby(["i", "j"]).night.nunique()

    sa = lines.merge(lines, on="account")
    sa = unordered(sa[sa.line_x != sa.line_y], "line_x", "line_y")
    s = sa.groupby(["i", "j"]).size().clip(upper=1)

    ev = pd.concat({"calls": c, "nights": n, "shared": s}, axis=1).fillna(0)
    return ev.reset_index()

Simplified. Inputs are generic event tables; the real signal set, windows and filters are not shown.

Step 2: Combine the evidence into weighted edges

The pair rows become an undirected graph: lines are nodes, and every pair with any evidence gets an edge whose weight summarizes how strongly the evidence points to family. The production weighting is not described here. The live model uses a form that makes the design intent explicit — each signal alone contributes little, and interaction terms reward signals that coincide.

c_ij = min(1, log(1 + calls_ij) / log(1 + κ))      saturating call signal
n_ij ∈ {0, 1}                                    regular night-time co-location
s_ij ∈ {0, 1}                                    same account

w_ij = a_c·c + a_n·n + a_s·s + b_cn·c·n + b_ns·n·s + b_cs·c·s

strong tie:   w_ij ≥ τ,   τ above anything a single signal can reach

import numpy as np
import networkx as nx

# Illustrative coefficients: no single signal can reach TAU on its own.
A = {"c": 0.6, "n": 0.6, "s": 0.5, "cn": 1.2, "ns": 0.8, "cs": 0.6}
TAU = 1.9

def tie_weight(calls, nights, shared, kappa=25, min_nights=3):
    c = np.minimum(1.0, np.log1p(calls) / np.log1p(kappa))   # saturating call signal
    n = (nights >= min_nights).astype(float)                  # regular night co-location
    s = (shared > 0).astype(float)                            # same account
    return (A["c"] * c + A["n"] * n + A["s"] * s
            + A["cn"] * c * n + A["ns"] * n * s + A["cs"] * c * s)

def build_graph(ev, all_lines):
    w = tie_weight(ev.calls, ev.nights, ev.shared)
    G = nx.Graph()
    G.add_nodes_from(all_lines)                               # isolated lines stay in
    G.add_weighted_edges_from(zip(ev.i, ev.j, w))
    return G

Simplified. Coefficients are illustrative, close to the live model's; production weights are not shown.

Why interactions rather than a plain sum? Every signal has a common false positive — the neighbour, the colleague, the employee on the account — and those false positives rarely coincide. Product terms let two moderate signals together outweigh one strong-looking signal alone, so the graph degrades gracefully where one signal is weak.

Step 3: Find communities with Louvain

Families look like small, dense communities in this graph, so community detection is the natural tool. Louvain maximizes modularity — the edge weight inside communities minus what a random graph with the same weighted degrees would put there — with a greedy two-phase loop.

Q = (1 / 2m) · Σ_ij [ w_ij − γ · k_i·k_j / 2m ] · δ(c_i, c_j)

phase 1   move each node i to the neighbouring community C with the largest gain
          ΔQ(i → C) = k_i,C / m − γ · Σ_tot(C) · k_i / 2m²
phase 2   collapse each community into one node; repeat until Q stops rising

k_i  weighted degree     m  total edge weight     k_i,C  weight from i into C
Σ_tot(C)  total degree of C     γ  resolution

At full subscriber scale the project used Parallel Louvain, which evaluates node moves concurrently before aggregating, so a graph of every line can be partitioned in one run. The single-machine version below shows the same algorithm; move_gain is the test phase 1 applies to every node.

import networkx as nx

def move_gain(k_i_in, k_i, sigma_tot, m, gamma=1.0):
    """Phase 1 test: ΔQ for moving node i (taken out on its own) into community C."""
    return k_i_in / m - gamma * sigma_tot * k_i / (2 * m * m)

def neighbourhoods(G, gamma=1.0, seed=0):
    """Both Louvain phases, repeated until modularity stops rising."""
    parts = nx.community.louvain_communities(
        G, weight="weight", resolution=gamma, threshold=1e-7, seed=seed)
    Q = nx.community.modularity(G, parts, weight="weight", resolution=gamma)
    comm = {v: k for k, part in enumerate(parts) for v in part}
    return comm, Q

Simplified, single machine. louvain_communities runs both phases; the production run used a parallel implementation.

Step 4: Identify homes inside each community

Run on its own, modularity optimization merges households. Merging two communities A and B with total degrees d_A and d_B, joined by tie weight l_AB, raises Q whenever:

ΔQ_merge = l_AB / m − γ · d_A·d_B / 2m²  > 0      ⇔      l_AB > γ · d_A·d_B / 2m

The right-hand side shrinks as the graph grows. In a graph of a whole city, d_A·d_B / 2m is tiny for two households of three people, so one friendship or two neighbours sharing a cell is enough to merge them. This is the resolution limit of modularity: it cannot see communities that are small relative to the whole graph. Raising γ moves the threshold, but one global value cannot suit low-rise streets and dense apartment blocks at once.

The answer is two stages. Louvain does what it is good at — carving the graph into tightly connected groups, the families and the social neighbourhoods around them. Homes are then identified inside each group from local evidence. In production that second stage was location-based household inference. The live model substitutes a strong-tie rule: inside a community, a household is a connected set of ties that clear τ.

import networkx as nx

def strong_tie_groups(G, comm, tau):
    """Live-model stand-in for location-based inference: lines joined by
    strong ties that stay inside one Louvain community."""
    H = nx.Graph()
    H.add_nodes_from(G)
    H.add_weighted_edges_from(
        (u, v, w) for u, v, w in G.edges(data="weight")
        if w >= tau and comm[u] == comm[v])
    return H, [set(c) for c in nx.connected_components(H)]

Simplified. The live model's stand-in for location-based inference.

Step 5: Cut bridges and split groups too large for one home

Strong-tie groups still occasionally chain two homes together — a grandparent who calls daily and stays over often, for example. Such chains usually hang on a single tie. The live model removes a bridge (an edge whose removal disconnects the group) when both sides keep at least two lines, weakest bridge first, and then splits any group larger than a plausible home by dropping its weakest ties until it falls apart.

import networkx as nx

def cut_bridges(H, group, min_side=2):
    """Cut strong ties that alone hold two would-be homes together."""
    S = H.subgraph(group).copy()
    cut = True
    while cut:
        cut = False
        for u, v in sorted(nx.bridges(S), key=lambda e: S.edges[e]["weight"]):
            w = S.edges[u, v]["weight"]
            S.remove_edge(u, v)
            if min(len(nx.node_connected_component(S, x)) for x in (u, v)) >= min_side:
                cut = True
                break                                    # bridges changed: recompute
            S.add_edge(u, v, weight=w)
    return S, [set(c) for c in nx.connected_components(S)]

def split_oversized(S, groups, max_size=6):
    """Drop the weakest ties of any group too large to be one home."""
    out, todo = [], list(groups)
    while todo:
        T = S.subgraph(todo.pop()).copy()
        for u, v, _ in sorted(T.edges(data="weight"), key=lambda e: e[2]):
            if len(T) <= max_size or not nx.is_connected(T):
                break
            T.remove_edge(u, v)
        parts = [set(c) for c in nx.connected_components(T)]
        (out if len(parts) == 1 else todo).extend(parts)
    return out

Simplified. nx.bridges lists edges whose removal disconnects the graph; the size cap is the live model's.

Why two lines on each side? A line attached by a single strong tie is often a genuine member — a teenager who mostly calls one parent. Cutting only where both sides look like homes of their own removes the chains without orphaning members.

Step 6: Score the partition against known households

Household inference produces a partition of lines, and partitions are best compared pair by pair: two lines placed in the same group are a true positive if they really live together. Pairwise precision says how often co-grouped lines belong together, so it falls when households are merged; pairwise recall says how many real co-residents were kept together, so it falls when households are split. Neither needs group IDs to be matched between the prediction and the reference.

n_gh  lines in predicted group g and reference household h

TP        = Σ_(g,h) C(n_gh, 2)
precision = TP / Σ_g C(n_g, 2)          recall = TP / Σ_h C(n_h, 2)
exact     = #{ (g, h) : n_gh = n_g = n_h }

from collections import Counter
from math import comb

def pair_scores(pred, truth):
    """pred, truth: dict line -> group. Scores a partition pair by pair."""
    joint = Counter((pred[v], truth[v]) for v in truth)
    size_p, size_t = Counter(pred[v] for v in truth), Counter(truth.values())
    pairs = lambda sizes: sum(comb(n, 2) for n in sizes)

    tp = pairs(joint.values())                  # together in both
    precision = tp / pairs(size_p.values())     # grouped together and really together
    recall = tp / pairs(size_t.values())        # really together and grouped together
    f1 = 2 * precision * recall / (precision + recall)
    exact = sum(1 for (g, h), n in joint.items() if n == size_p[g] == size_t[h])
    return {"precision": precision, "recall": recall, "f1": f1, "exact": exact}

Simplified. In the live model the reference is the planted city.

The live model reports pairwise F1, households recovered exactly and lines placed away from most of their household, for the billing-account baseline and for the detected households, on every generated city.

Step 7: Keep a household ID from month to month

A clustering that changes every month is unusable by a campaign team. The project introduced a head-of-household concept and built an ID structure on it, so that a household keeps its identifier as members join, leave and move, and family changes can be tracked over time.

The live model reruns the whole pipeline on the following month — some lines churn, a few households move, some adults move out — and carries IDs forward with a simple rule: the head is the household's longest-tenured line, and the ID survives if the head is still present and the head's new group overlaps the old one by at least half (Jaccard). Otherwise the group gets a new ID, which is itself a record of change.

def carry_ids(prev, curr, tenure, new_id, min_jaccard=0.5):
    """prev: {household_id: set of lines} last month; curr: list of sets this month.
    The head (longest-tenured line) carries the ID if the household mostly held."""
    where = {v: k for k, g in enumerate(curr) for v in g}
    ids = {}
    for hid, members in prev.items():
        head = max(members, key=lambda v: tenure[v])
        if head not in where:
            continue                                   # head left: no carry-over
        k = where[head]
        alive = {v for v in members if v in where}
        jaccard = len(alive & curr[k]) / len(alive | curr[k])
        if jaccard >= min_jaccard and k not in ids:
            ids[k] = hid
    return {(ids[k] if k in ids else new_id()): g for k, g in enumerate(curr)}

Simplified, as in the live model. new_id() issues a fresh identifier; the production ID scheme is not shown.

Why anchor on a person rather than on the group? Group membership is exactly what changes. A head gives the ID something stable to follow, and the overlap test decides when a household has changed enough to count as a new one.

Results

The model created a foundation for customer understanding at the family and household level, enabling more realistic segmentation, bundled-product strategy, family-level campaigns and long-term relationship analysis.

Because the household ID persists across runs, it works as a shared dimension: other teams can join their own data to it and look at the same home over months rather than at a fresh clustering each time.

Lessons learned

• Use community detection for what it is good at. Louvain partitions a very large graph quickly into tightly connected groups; it does not resolve groups of two or three. The second, local stage is part of the design, not a patch.
• Design edge weights around failure modes. Each signal has a typical false positive. Weights that reward coinciding signals degrade gracefully when one signal is weak, as night-time location is in apartment blocks.
• Score partitions pair by pair. Pairwise precision and recall need no matching of group IDs and show directly whether the errors are merges or splits.
• The identifier is the product. A stable household ID anchored to a head of household is what turned a periodic analysis into something campaigns and other teams could use.

Conclusion

Households are not in the data, but their traces are: calls, nights spent in the same place, shared accounts. Treating families and households as small communities in a weighted graph of those traces, finding the communities with Parallel Louvain, identifying homes inside them and anchoring each to a head of household produced a household view of a customer base that had been visible only as individual lines.

The same pattern — aggregate pairwise evidence, partition with a scalable global method, refine locally where the global objective is blind, and keep identities stable across runs — carries over to other entity-resolution problems, such as linking accounts or devices that belong to the same customer.

Limitations

• Inferred households are probabilistic; they are a basis for offers and analysis, not a record of who lives where, and the use of location and call signals was governed by the operator's privacy policy.
• Single-person households and close neighbours are the hard cases; the live model's dense setting shows the error rate rising there.
• The live model runs plain Louvain on about a thousand generated lines with three planted signals and uses a strong-tie rule with bridge cuts in place of location-based household inference; the production system ran a parallel implementation over a far larger graph with richer signals.

About the demo and confidentiality

Lines, calls, locations, accounts and households in the embedded model are generated from a planted structure. No subscriber, call, location or account data from any operator appears in this post, and the real signal set, weights and thresholds are not described. Code is simplified and written for illustration; the libraries it uses are not a description of the production stack.