如何用MapReduce(Hadoop)从社交网络数据中查找非对称关注对？

Great question—this is a common pattern in social network graph analysis, and MapReduce is perfect for handling it at scale without messing up the results. Let's break this down into clear Mapper and Reducer logic, plus the core idea behind why this works.

Core Idea #

We need to identify pairs where A follows B, but B does not follow A. The key insight is to treat each follow relationship as a bidirectional candidate, then group and check if the reverse relationship exists. By normalizing each pair into a sorted "key" (so (A,B) and (B,A) share the same key if we sort them), we can efficiently check for the presence of both directions in the Reducer.

Mapper Implementation #

The Mapper's job is to take each raw (follower, followee) pair and generate normalized entries that let us compare both directions later.

Input Format #

Each input line is a single follow relationship: follower_id\tfollowee_id (e.g., alice\tbob means Alice follows Bob).

Mapper Logic #

For each input pair (F, L) (F = follower, L = followee):

1. Normalize the pair: Sort F and L lexicographically (or numerically, depending on your ID type) to create a shared key. Let's call this sorted pair (X, Y) where X <= Y.
2. Output a key-value pair: Use the sorted (X,Y) as the key, and the original relationship (e.g., F->L) as the value.

This ensures every follow relationship and its possible reverse are grouped under the same sorted key, so we can compare them in the Reducer.

Sample Mapper Code (Java) #

public class AsymmetricPairsMapper extends Mapper<LongWritable, Text, Text, Text> {
    @Override
    protected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {
        String[] parts = value.toString().split("\t");
        if (parts.length != 2) return; // Skip invalid lines
        
        String follower = parts[0];
        String followee = parts[1];
        
        // Create sorted key to group both directions
        String sortedKey;
        if (follower.compareTo(followee) <= 0) {
            sortedKey = follower + "," + followee;
        } else {
            sortedKey = followee + "," + follower;
        }
        
        // Output original relationship as value
        context.write(new Text(sortedKey), new Text(follower + "->" + followee));
    }
}

Reducer Implementation #

The Reducer will receive all relationships for each sorted key, then check if both directions exist. If only one direction is present, that's our asymmetric pair.

Reducer Logic #

1. Track existing relationships: For a key (X,Y), check if both X->Y and Y->X are present in the values.
2. Identify asymmetric pairs:
   • If only X->Y exists: Output X\tY (since X follows Y, Y doesn't follow X)
   • If only Y->X exists: Output Y\tX (since Y follows X, X doesn't follow Y)
   • If both exist: Do nothing (this is a symmetric mutual follow pair)

Sample Reducer Code (Java) #

public class AsymmetricPairsReducer extends Reducer<Text, Text, Text, NullWritable> {
    @Override
    protected void reduce(Text key, Iterable<Text> values, Context context) throws IOException, InterruptedException {
        boolean hasForward = false;
        boolean hasReverse = false;
        String forwardPair = null;
        String reversePair = null;
        
        String[] keyParts = key.toString().split(",");
        String X = keyParts[0];
        String Y = keyParts[1];
        
        for (Text val : values) {
            String rel = val.toString();
            if (rel.equals(X + "->" + Y)) {
                hasForward = true;
                forwardPair = X + "\t" + Y;
            } else if (rel.equals(Y + "->" + X)) {
                hasReverse = true;
                reversePair = Y + "\t" + X;
            }
        }
        
        // Output only asymmetric pairs
        if (hasForward && !hasReverse) {
            context.write(new Text(forwardPair), NullWritable.get());
        } else if (!hasForward && hasReverse) {
            context.write(new Text(reversePair), NullWritable.get());
        }
    }
}

Key Notes to Avoid Mistakes #

• Normalization is critical: By sorting pairs into a shared key, we ensure (A,B) and (B,A) end up in the same Reducer—this prevents missing reverse relationships that might be processed separately.
• Deduplicate first: If your input has duplicate follow pairs (e.g., alice\tbob appearing twice), add a deduplication step in the Mapper (e.g., use a Set to track seen pairs per task) to avoid false positives.
• Scalability: This approach only shuffles one entry per input pair, making it efficient even for billions of relationships.

内容的提问来源于stack exchange，提问作者Jiho Choi