What's the longest question duplicate chain on SE?

TLDR; 10 Links¹ starting from any of:

• https://apple.meta.stackexchange.com/q/455
• https://gaming.meta.stackexchange.com/q/1892
• https://drupal.meta.stackexchange.com/q/2159
• Is it possible to change the "integral-dependance" tag into "integral-dependence"?

Intro

Honestly, this was really fun to work through. I had to reevaluate quite a lot of assumptions through this process, like all sites have duplicate questions and that every question closed as a duplicate has a dupe target (both of which are incorrect).

SEDE

I started out on SEDE and made it through any number of variations which all ultimately did not do what was needed. I couldn't get any query to complete on Stack Overflow and couldn't create a query that would run network-wide. I was only able to pull limited sections of sites before it timed out. This query represents one of many many many attempts at solving this problem there and covers less than half of the available sites.

Ultimately, I decided it would be easier to just step away from SEDE and move to the data dumps. I used the 2023-09-12 Stack Exchange Data Dump which is the most current version at this time.

Data Dump Process

I pulled down all the data and pulled out just the PostLinks.xml file from every site. I renamed the files so that they follow the format of {site}-PostLinks.xml and put them in a folder called "PostLinks." A really great benefit of using the data dumps instead of SQL for this is that I can solve it graphically as longest path problem instead of using a recursive lookup.

Approach

Ultimately, I ended up using networkx's dag_longest_path to find the "longest path" per site. Please note, that this function only returns one instance of the longest path so there may be several paths of that length which are not visible here. This was a huge time saver and does fine to answer the question of "What's the longest question duplicate chain on SE?"

Results

At this time, considering the information available the longest duplicate chain is 10 links. This occurs on multiple different sites.

See the following summary table of the top 15 values network wide (unfortunately the full result set is 85k characters and won't fit in an answer on SE, one of the main drawbacks of not using SEDE here):

Network-wide

You'll likely notice rather quickly looking through these posts that the majority of duplicate chains this long are the result of year-to-year events which were closed as duplicates of the succeeding year and exist on meta sites.

The one here on MSE is a rather special case because it was migrated to MSO and the duplicate chain continues there. Which makes it technically 11 links (one of which is a migration) and 10 links between duplicate targets (this is the ¹ in the TLDR and the asterisk in the table) though it is split between two sites. This approach wouldn't successfully track migrations across network, so it is possible there are longer chains than the above including migrated then closed questions.

Main sites only (excluding MSE)

By ignoring meta sites we can mostly exclude these types of year-to-year closures. Here are the top 15 results from main sites (excluding MSE):

Again, there may be more than one chain of the same length on the site. This approach only found one instance of the longest path.

Infinite Cycles

While here I also found 103 circular duplicates (since they needed to be removed before finding a "longest path"). Technically all of the following are the longest path with length of infinite.

I also found 17 self duplicates which appear to be a remnant of a very old duplicate closure process wherein the question was just closed because the question already exists but relied on a user to either comment with a link or edit the link into the post themselves. This appears to have been programmatically stored as a self-referencing duplicate link. They all exist on Stack Overflow have been closed for ~14 years.

Here is the approach I used to find these:

from glob import glob
from pathlib import Path
from typing import List, Generator

import networkx as nx
import pandas as pd
from tqdm import tqdm


def make_df_from_xml(fp: Path) -> pd.DataFrame:
    df = pd.read_xml(fp)
    df = df.loc[
        df['LinkTypeId'].eq(3),  # Only care about duplicate link types
        ['PostId', 'RelatedPostId']
    ].copy(deep=True)
    return df


def save_cyclic_deps(dupe_cycles: List[object]) -> None:
    if not dupe_cycles:
        return

    p = Path('./raw_cycle_output.csv')
    if not p.exists():
        pd.DataFrame(dupe_cycles).to_csv(p, index=False)
    else:
        pd.concat([
            pd.read_csv(p),
            pd.DataFrame(dupe_cycles)
        ]).drop_duplicates().sort_values(
            by='Cycle Length',
            ascending=False
        ).to_csv(p, index=False)


def ids_list_to_str(ids: List[int]) -> str:
    return ' -> '.join(map('{:.0f}'.format, ids))


def create_link_to_start(site: str, ids: List[int]) -> str:
    if not ids:
        return ''
    return f'https://{site}/q/{ids[0]}'  # Link to start of path/cycle


def process_individual_site(site_name: str, df: pd.DataFrame) -> List[int]:
    DG: nx.DiGraph = nx.from_pandas_edgelist(df, source='PostId', target='RelatedPostId', create_using=nx.DiGraph())

    dupe_cycles = []

    # Remove any circular dependencies
    for coord in list(nx.simple_cycles(DG)):
        dupe_cycles.append({
            'Site Name': site_name,
            'Cycle Length': len(coord),  # Technically infinite
            'Link to start': create_link_to_start(site_name, coord),
            'Cycle Path': ids_list_to_str(coord)
        })
        if len(coord) == 1:
            # For Stack Overflow
            # Duplicate closures used to just be "This question already has answers here"
            # and a user would have to manually edit or comment with a link
            # this appears to be stored programmatically as a self cycle
            s, = coord
            DG.remove_edge(s, s)
        else:
            s, *_, e = coord
            # Remove back edge
            DG.remove_edge(e, s)

    save_cyclic_deps(dupe_cycles)

    res = nx.dag_longest_path(DG)
    return res


def get_longest_path_for_all_sites() -> Generator[dict]:
    progress_glob = tqdm(glob(r'.\PostLinks\*-PostLinks.xml'))

    for post_links in progress_glob:
        p = Path(post_links)
        [site, *_] = p.stem.split('-')

        # Update progress with current site
        progress_glob.set_postfix_str(site)

        longest_path = process_individual_site(site, make_df_from_xml(p))

        yield {
            'Site Name': site,
            'Number of links': len(longest_path) - 1,  # Edge count instead of node count
            'Link to start': create_link_to_start(site, longest_path),
            'Path': ids_list_to_str(longest_path)
        }


def main() -> None:
    pd.DataFrame(
        get_longest_path_for_all_sites()
    ).sort_values(
        by='Path Length',
        ascending=False
    ).to_csv('./raw_aggregated_output.csv', index=False)


if __name__ == '__main__':
    main()