[HADOOP] 하둡지도 축소 Google 웹 그래프

하둡지도 축소 Google 웹 그래프

우리는 과제로서지도를 생성하는 작업을 Google 웹 그래프 목록의 노드 n에서 3 개의 홉 (hop)으로 이동할 수있는 각 노드 n에 대해 출력 할지도 축소 함수를 부여했습니다. (실제 데이터는 http://snap.stanford.edu/data/web-Google.html에서 확인할 수 있습니다.) 다음은 목록에있는 항목의 예입니다.

1 2 
1 3 
2 4 
3 4 
3 5 
4 1 
4 5 
4 6 
5 6 

위의 예제 그래프는 다음과 같습니다.

위의 단순화 된 예에서 노드 1의 예와 같은 경로는 다음과 같습니다. α [1 → 2 → 4 → 1], [1 → 2 → 4 → 5], [1 → 2 → 4 → 6], [1 → 3 → 4 → 5] 1], [1 → 3 → 4 → 5] → [1 → 3 → 4 → 6] → [1 → 3 → 5 → 6] 따라서 맵 축소는 노드 1에 대해 정점 1,5,6 ( (a) 각 꼭지점은 한 번만 계산되어야하며, (b) 예를 들어 [1 -> 2 -> 4 -> 1]과 [1 -> 3 -> 4> 1]처럼 길이가 3 인 원형 경로가있는 경우에만 현재 정점을 포함합니다.

나는 그래프 이론과 알고리즘에 대한 지식이 필요하다고 생각하고 그와 관련된 어떠한 것도 배웠지 않았기 때문에 나는 매우 길다.

누군가가 나에게 올바른 방향을 제시 할 수 있다면 크게 감사 할 것입니다. (나는 최단 경로 이론 등을 들여다 보았다.하지만이 특정 운동에 유용 할 지 모르겠다.)

미리 감사 드리며 좋은 휴일 시즌을 보내십시오.

편집하다

adjucency 목록을 만들려고하지만 출력이 "vertexID" "node1 node2 node3 node4 ..."라고 예상하는 동안 출력 파일에서 내 감속기가 각 꼭지점 ID의 목록을 세 쌍으로 나눕니다.

예를 들어 내가 Z, X, C, V, B, N, M, G, H, J, K, L에 연결하는 정점 A를 가지고 있다면

Z, X, C

V, B, N

M, G, H

J, K, L

내 매퍼와 감속기는 다음과 같습니다.

public class AdjacentsListDriver extends Configured implements Tool {

    @Override
    public int run(String[] args) throws Exception {



        Configuration conf = getConf();
        Job job = Job.getInstance(conf);
        job.setJobName("Test driver");
        job.setJarByClass(AdjacentsListDriver.class);

        String[] arg0 = new GenericOptionsParser(conf, args).getRemainingArgs();
        if (arg0.length != 2) {
            System.err.println("Usage: hadoop jar <my_jar> <input_dir> <output_dir>");
            System.exit(1);
        }

        Path in = new Path(arg0[0]);
        Path out = new Path(arg0[1]);

        FileInputFormat.setInputPaths(job, in);
        FileOutputFormat.setOutputPath(job, out);

        job.setMapperClass(ListMapper.class);
        job.setReducerClass(ListReducer.class);

        job.setInputFormatClass(TextInputFormat.class);
        job.setOutputFormatClass(TextOutputFormat.class);

        job.setOutputKeyClass(Text.class);
        job.setOutputValueClass(Text.class);    
        job.waitForCompletion(true);

        return 0;
    }

    public static void main(String[] args) throws Exception {
        int res = ToolRunner.run(new Configuration(), new AdjacentsListDriver(), args);
        System.exit(res);

    }



}





/**
 * @author George
 * Theoretically this takes a key(vertexID) and maps all nodes that are connected to it in one hop....
 *
 */
public class ListMapper extends Mapper<LongWritable, Text, Text, Text> {

    private Text vertexID = new Text();
    //private LongWritable vertice= new LongWritable(0);
    private Text vertice=new Text();

    public void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {

        String line = value.toString();
        StringTokenizer itr = new StringTokenizer(line,"\n");
        StringTokenizer itrInside;

        //vertice=new LongWritable(Long.valueOf(value.toString()).longValue());


        while (itr.hasMoreTokens()) {
            if(itr.countTokens() > 2){

            }//ignore first line ??
            else{
                itrInside=new StringTokenizer(itr.toString());
                vertexID.set(itr.nextToken());

                while(itrInside.hasMoreTokens()){               
                    vertice.set(itrInside.nextToken());
                    context.write(vertexID, value);
                }           
            }
        }

    }

}

@override
public class ListReducer extends Reducer<Text, Text, Text, Text>{
    public void reduce(Text key, Iterable<Text> values, Context context) throws IOException, InterruptedException {

        String vertices="";

        for (Text value : values) {
            if(vertices=="")
                vertices+=value.toString();
            else
                vertices=vertices+","+value.toString();         
        }

        Text value=new Text();
        value.set(vertices);
        context.write(key, value);

    }

}

해결법

1. ==============================

   1.귀하의 (숙제) 과제이기 때문에 Java / Hadoop 솔루션은 포함하지 않겠지 만 MapReduce를 사용한 그래프 계산 개념을 좀 더 명확하게 만들어서 직접 구현할 수 있습니다.

   귀하의 (숙제) 과제이기 때문에 Java / Hadoop 솔루션은 포함하지 않겠지 만 MapReduce를 사용한 그래프 계산 개념을 좀 더 명확하게 만들어서 직접 구현할 수 있습니다.

   당신은 각 꼭지점에 대해 정확하게 n-hop 거리에있는 꼭지점을 원합니다. 최단 경로 알고리즘을 보면서 올바른 길을 가고 있었지만 간단한 너비 우선 탐색으로 쉽게 해결할 수 있습니다.

   그러나 MapReduce를 사용하여 그래프를 처리 할 때 정점 사이를 지나가는 메시지를 조금 더 깊이 들어가야합니다. 그래프 알고리즘은 대개 맵 및 축소 스테이지가 다음과 같은 할당을 갖는 여러 작업으로 표현됩니다.

   각 작업은 결과에 도달하거나 포기하기 전까지 항상 이전 작업의 출력에서 ​​작동합니다.

   데이터 준비

   그래프 알고리즘을 실제로 실행하기 전에 데이터가 인접 목록 형태인지 확인하십시오. 다음 반복 알고리즘을 훨씬 쉽게 구현할 수 있습니다.

   따라서 인접성 튜플 대신 꼭지점 ID별로 그룹화해야합니다. 다음은 몇 가지 의사 코드입니다.

   map input tuple (X, Y): 
      emit (X, Y)
   
   reduce input (X, Y[]) :
     emit (X, Y[])
   

   기본적으로 꼭지점 ID별로 그룹화하므로 입력 데이터는 이웃들 (특정 키 꼭지점 ID에서 도달 할 수있는 버텍스 ID 목록)에 대한 키 (버텍스 ID)입니다. 자원을 절약하려면 감속기를 결합기로 사용할 수 있습니다.

   연산

   이미 언급 한 것처럼 폭 넓은 첫 번째 검색 알고리즘 만 필요합니다. 그래프의 모든 버텍스에 대해 광범위한 첫 번째 검색 알고리즘을 실행합니다. 이웃에 도달하면 시작점에서 얼마나 멀리 떨어져 있는지 알려주는 홉 카운터를 증가시킵니다 (가장 짧은 경로 알고리즘의 가장 간단한 경우, 에지 가중치가 1 일 때).

   간단한 그래프로 설명하는 간단한 그림을 보여 드리겠습니다. 오렌지는 방문한 것을 의미하고 푸른 색은 방문하지 않고 녹색은 우리의 결과입니다. 괄호 안에는 홉 카운터가 있습니다.

   모든 반복에서 우리는 모든 버텍스에 대해 홉 카운터를 설정하고 있습니다. 새로운 꼭지점을 친다면 우리는 그것을 하나씩 증가시킬 것입니다. n 번째 꼭지점에 도달하면 나중에 조회 할 수 있도록 표시합니다.

   MapReduce로 배포

   모든 정점에 대해 폭 넓은 첫 번째 검색을 실행하는 것은 실제로 낭비적인 것처럼 보이지만이를 병렬 처리하여 더 잘 수행 할 수 있습니다. 여기에 메시지가 전달됩니다. 위의 그림에서와 같이 매핑 단계에서 얻는 모든 정점은 처음에는 다음 페이로드가 포함 된 메시지를 이웃 사람에게 보냅니다.

   HopMessage: Origin (VertexID) | HopCounter(Integer)
   

   첫 번째 반복에서 우리는 계산을 시작하기 위해 이웃에게 메시지를 보내려고합니다. 그렇지 않으면 그래프 또는 수신 메시지를 프록시 처리합니다.

   따라서 데이터 준비 후 첫 직장에서 맵과 축소는 다음과 같이 보입니다.

   map input (VertexID key, either HopMessage or List<VertexID> adjacents):
     if(iterationNumber == 1): // only in the first iteration to kick off
        for neighbour in adjacents:
           emit (neighbour, new HopMessage(key, 0))
     emit (key, adjacents or HopMessage) // for joining in the reducer
   

   감속기는 이제 그래프와 메시지 사이의 단순한 조인을 수행합니다. 주요하게 이웃으로 정점을 가져 와서 그 입력을 이끌어냅니다 (단순한 그래프를 사용).

   1 2 // graph 
   2 1 // hop message
   2 3 // graph
   3 1 // hop message
   3 4 // graph
   4 1 // hop message
   4 - // graph
   

   감속기 단계에서 우리는 이웃에게 메시지를 다시 전달하고 홉 카운터가 증가한 후에 이미 3에 도달했는지 확인합니다.

   reducer input(VertexID key, List<either HopMessage or List<VertexID> neighbours> values):
    for hopMessage in values:
       hopMessage.counter += 1
       if (hopMessage.counter == 3) 
          emit to some external resource (HopMessage.origin, key)
       else 
          for neighbour in neighbours of key:
             emit (neighbour, hopMessage)
       emit (key, neighbours)
   

   보시다시피, 여기에 정말 엉망이 될 수 있습니다. 두 가지 종류의 메시지를 관리 한 다음 정확히 3 홉 떨어진 꼭지점을 추적하는 외부 리소스에 쓸 필요가 있습니다.

   전송할 HopMessages가있는 한 반복되는 작업을 예약합니다. 이 경우 홉 카운터를 무한대로 늘리므로 그래프의 사이클에 문제가 발생하기 쉽습니다. 따라서 모든 메시지 (매우 낭비)로 전체 경로를 전송하거나 단순히 반복 횟수를 제한하는 것이 좋습니다. n = 3 인 경우 3 번 이상의 작업 반복이 필요하지 않습니다.

   Hadoop의 각 문제를 다루는 방법에 대한 예제를 제공 할 많은 블로그와 프로젝트가 있습니다. 적어도 필자는 내 블로그에서 MapReduce의 그래프 처리에 대해 썼으며 내 github에서 몇 가지 예를 찾을 수 있습니다.

   출력 데이터 정리

   결국에는 꼭지점 -> 꼭지점 매핑을 포함하는 파일들이있을 것입니다. 준비 과정에서했던 것과 동일한 방법으로 줄일 수 있습니다.

   Pregel을 사용하여 Niftier 방법

   그래프를 다루는 덜 성가신 방법은 그래프 계산을 표현하는 프레 겔 (Pregel) 방식을 사용하는 것입니다. Pregel은 정점 중심 모델을 사용하고 있으며 이러한 폭이 넓은 첫 번째 계산을보다 쉽게 ​​표현할 수 있습니다.

   다음은 Apache Hama를 사용하는 위 알고리즘의 간단한 예입니다.

     public static class NthHopVertex extends Vertex<Text, NullWritable, HopMessage> {
   
       @Override
       public void compute(Iterable<HopMessage> messages) throws IOException {
         if (getSuperstepCount() == 0L) {
           HopMessage msg = new HopMessage();
           msg.origin = getVertexID().toString();
           msg.hopCounter = 0;
           sendMessageToNeighbors(msg);
         } else {
           for (HopMessage message : messages) {
             message.hopCounter += 1;
             if (message.hopCounter == 3) {
               getPeer().write(new Text(message.origin), getVertexID());
               voteToHalt();
             } else {
               sendMessageToNeighbors(message);
             }
   
           }
         }
       }
     }
   

   BETWEEN 예제에서 만든 새 그래프는 다음과 같습니다.

   1=[1, 5, 6]
   2=[2, 3, 6]
   3=[2, 3, 6]
   4=[4, 5]
   

   하마 그래프 전체 구현은 다음과 같습니다.

   https://github.com/thomasjungblut/tjungblut-graph/blob/master/src/de/jungblut/graph/bsp/NthHop.java

from https://stackoverflow.com/questions/20774253/hadoop-map-reduce-for-google-web-graph by cc-by-sa and MIT license