Как равномерно пробовать большой график?

Question

У меня есть большой график, который имеет около 4M узлов. Граф состоит из двух файлов, один из которых содержит имена узлов и один из них содержит ребра (каждая строка представляет собой один край). Я хочу равномерно пробовать узлы графа и придумывать образец размером до 15% всего графика. Учитывая размер графика, каков наилучший (или, возможно, возможный) способ создания такого образца?

Answer 1

Используйте этот код Java, чтобы выбрать 15% вершин случайно:

import java.io.IOException; 
import java.util.*; 

import org.apache.hadoop.fs.Path; 
import org.apache.hadoop.conf.*; 
import org.apache.hadoop.io.*; 
import org.apache.hadoop.mapreduce.*; 
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat; 
import org.apache.hadoop.mapreduce.lib.input.TextInputFormat; 
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat; 
import org.apache.hadoop.mapreduce.lib.output.TextOutputFormat; 

public class RandomSample { 

public static class Map extends Mapper<LongWritable, Text, Text, Text> { 
    private Text word = new Text(); 

    public void map(LongWritable key, Text value, Context context) 
    throws IOException, InterruptedException { 
     if (Math.random()<0.15) 
      context.write(value,null); 
     else 
      context.write(null,null); 
    context.write(value,null); 
    } 
} 

public static void main(String[] args) throws Exception { 
    Configuration conf = new Configuration(); 

    Job job = new Job(conf, "randomsample"); 
    job.setJarByClass(RandomSample.class); 

    job.setOutputKeyClass(Text.class); 
    job.setOutputValueClass(IntWritable.class); 

    job.setOutputKeyClass(Text.class); 
    job.setOutputValueClass(Text.class); 
    job.setInputFormatClass(TextInputFormat.class); 
    job.setOutputFormatClass(TextOutputFormat.class); 

    job.setNumReduceTasks(0); 

    FileInputFormat.addInputPath(job, new Path(args[0])); 
    FileOutputFormat.setOutputPath(job, new Path(args[1])); 

    job.waitForCompletion(true); 
} 

} 

И использовать этот Баш скрипт, чтобы запустить его

echo "Running Job" 
hadoop jar RandomSample.jar RandomSample $1 tmp 
echo "copying result to local path (RandomSample)" 
hadoop fs -getmerge tmp RandomSample 
echo "Clean up" 
hadoop fs -rmr tmp 

Например, если мы называем random_sample.sh скрипт , чтобы выбрать 15% из папки/например /, просто запустите

./random_sample.sh /example/ 

Затем, вы можете использовать простой grep операция по второму файлу для выбора только ребер, содержащих случайно выбранные вершины