Группировка подграфов по related_user_id без ложной связности

Как избежать перегруппировки: группируйте подграфы по цепочкам related_user_id→actor_user_id, а не по общим акторам. Разбор с примером на pandas и networkx.

Когда вы помечаете взаимодействия между пользователями идентификатором подграфа, напрашивается простой подход — посчитать связные компоненты в графе actor_user_id → related_user_id. Но есть подводный камень: общие акторы часто выступают в роли хабов, сворачивая множество несвязанных рёбер в одну гигантскую компоненту. Если ваша цель — объединять только те строки, у которых действительно есть пути связи на стороне related_user_id, стандартные компоненты слабой связности в топологии актор → связанный приведут к избыточной группировке.

Как воспроизвести проблему

Ниже приведён минимальный пример, который повторяет ситуацию, когда один и тот же актор формирует чрезмерно крупную компоненту, хотя ветви по related_user_id не пересекаются:

import pandas as pd
import networkx as nx

records = pd.DataFrame({
    'properties_id': ['A', 'A', 'A', 'A'],
    'global_journey_id': ['A1', 'A1', 'A1', 'A1'],
    'actor_user_id': ['abc', 'abc', 'pat', 'abc'],
    'related_user_id': ['def', 'efg', 'def', 'lal'],
})

net = nx.DiGraph()
net.add_edges_from(zip(records['actor_user_id'], records['related_user_id']))
parts = list(nx.weakly_connected_components(net))

Поскольку узел abc встречается в нескольких рёбрах, слабая связность связывает всё воедино. Это противоположно замыслу: группировать взаимодействия следует только тогда, когда их узлы related_user_id связаны — напрямую или через цепочки совместных появлений, — а не просто потому, что у них один и тот же actor_user_id.

Что здесь считается общей связью

Правило группировки строже, чем обычная связность. Две строки относятся к одному подграфу, если их значения related_user_id соединены реальной цепочкой совместных появлений под акторами. Если два ребра совпадают только по actor_user_id, а их ветви related_user_id нигде не соприкасаются, они должны оставаться в разных подграфах. Иными словами, узлы-акторы не должны работать как автомагистрали, сливающие несвязанные ветви; для объединения должна пересекаться именно сторона related.

Практический способ соблюсти правило

Надёжный подход — поменять точку зрения. Вместо того чтобы соединять actor_user_id → related_user_id и брать компоненты, смотрите со стороны related в сторону акторов и соединяйте только там, где есть явные пути. Это достигается обходом рёбер в направлении related_user_id → actor_user_id и группировкой только тех пар рёбер, которые реально достижимы в этом направлении. Так общий актор не сможет слить ветви, если на стороне related_user_id нет связи.

Двигайтесь от related_user_id → actor_user_id и назначайте подграфы только там, где есть явные связи; не группируйте лишь по общим акторам.

Реализация

Ниже приведён фрагмент, который группирует в пределах properties_id и global_journey_id, строит направленную карту переходов от related_user_id к actor_user_id, исследует достижимые цепочки рёбер и сопоставляет метку sub_graph исходным строкам. Логика программы сохраняет желаемое поведение и не сводит несвязанные ветви related_user_id под общим актором.

import pandas as pd
from collections import defaultdict, deque

sample = {
    'properties_id': ['A', 'A', 'A', 'A'],
    'global_journey_id': ['A1', 'A1', 'A1', 'A1'],
    'actor_user_id': ['abc', 'abc', 'pat', 'abc'],
    'related_user_id': ['def', 'efg', 'def', 'lal'],
}
frame = pd.DataFrame(sample)

out_rows = []
batches = frame.groupby(['properties_id', 'global_journey_id'])

for (pid, jid), chunk in batches:
    hop_map = defaultdict(list)
    for _, rec in chunk.iterrows():
        hop_map[rec['related_user_id']].append(rec['actor_user_id'])

    pair_keys = [frozenset([rec['actor_user_id'], rec['related_user_id']]) for _, rec in chunk.iterrows()]
    pair_set = set(pair_keys)

    seen_pairs = set()
    pair2sg = {}
    sg_id = 1

    for pair in pair_set:
        if pair in seen_pairs:
            continue
        a, b = list(pair)
        seed = b if b in hop_map else a
        if seed not in hop_map:
            continue

        q = deque([seed])
        cluster_pairs = set()

        while q:
            cur = q.popleft()
            for nxt in hop_map.get(cur, []):
                candidate = frozenset([cur, nxt])
                if candidate in pair_set and candidate not in seen_pairs:
                    seen_pairs.add(candidate)
                    cluster_pairs.add(candidate)
                    if nxt in hop_map:
                        q.append(nxt)

        for pr in cluster_pairs:
            pair2sg[pr] = sg_id

        sg_id += 1

    for _, rec in chunk.iterrows():
        k = frozenset([rec['actor_user_id'], rec['related_user_id']])
        label = pair2sg.get(k, None)
        out_rows.append({
            'properties_id': rec['properties_id'],
            'global_journey_id': rec['global_journey_id'],
            'actor_user_id': rec['actor_user_id'],
            'related_user_id': rec['related_user_id'],
            'sub_graph': label
        })

result_df = pd.DataFrame(out_rows)
result_df = result_df.sort_values(by=['properties_id', 'global_journey_id', 'sub_graph'])
print(result_df)

Это сохраняет требуемую семантику: два взаимодействия попадают в один подграф только тогда, когда их узлы related_user_id соединены явными путями совместных появлений под акторами. Общий актор сам по себе не запускает слияние.

Почему это стоит дополнительных усилий

В графовой аналитике пользовательских сценариев или журналов взаимодействий присвоение компонент напрямую влияет на последующую агрегацию, оповещения и отчётность. Если хабы вроде actor_user_id сводят несвязанные ветви, метрики размываются между независимыми взаимодействиями, а сортировка инцидентов становится шумной. Переориентируя обход к related_user_id и ограничивая группировку явной связностью, вы получаете подграфы, согласованные с семантикой общего контекста, а не с артефактами произвольной топологии.

Выводы

Выбирайте топологию графа, которая точно выражает ваше правило группировки. Когда критерий — пересечение на стороне related_user_id, а не общие акторы, не считайте компоненты по наивному графу actor → related. Вместо этого обходите related_user_id → actor_user_id, выводите связные наборы рёбер в этом направлении и возвращайте метки sub_graph в исходные строки. Так вы избегаете перегруппировки, сохраняете независимые ветви изолированными и получаете подграфы, соответствующие задуманным связям.