KR101441099B1

KR101441099B1 - 광고주와 사용자 연관

Info

Publication number: KR101441099B1
Application number: KR1020097025088A
Authority: KR
Inventors: 슈미트 발루자; 유시 징; 단다파니 시바쿠마르; 제이 야그닉
Original assignee: 구글 인코포레이티드
Priority date: 2007-05-01
Filing date: 2008-05-01
Publication date: 2014-11-03
Anticipated expiration: 2028-05-01
Also published as: US20110112916A1; US7904461B2; KR20100027121A; US20080275899A1; BRPI0811477A2; WO2008137590A2; US8572099B2; WO2008137590A3

Abstract

본 명세서의 주제는, 다른 것들 중에서도, 소셜 네트워크의 사용자에 의하여 생성된 컨텐츠에 기초하여 컨텐츠 기반의 키워드를 생성하는 단계를 포함하는 방법으로 구현될 수 있다. 본 방법은 3자에 의해 지정된 하나 이상의 용어에 기초하는 3자 선택형 키워드와 일치하는 컨텐츠 기반 키워드를 포함하는 라벨로, 사용자의 표시인 사용자 노드를 포함하는 노드를 라벨링하는 단계를 포함한다. 본 방법은 또한 각각의 노드에 대하여, 관계에 의해 상기 노드에 관련된 이웃하는 노드와 연관된 라벨의 가중치에 기초하여 상기 라벨에 대한 가중치를 출력하는 단계를 포함한다.

Description

광고주와 사용자 연관{ADVERTISER AND USER ASSOCIATION}

본 즉각적인 명세서는 사용자의 관심을 추론하는 것에 관련된다.

소셜 네트워크는 사용자가 자신에 대한 정보를 포스트(Post)하고 자신의 친구, 가족 및 동료 등 다른 사람들과 통신할 수 있도록 하는 것이 가능하다. 일부 소셜 네트워크는 사용자가 다른 사용자들과 친구 관계를 지정할 수 있도록 한다. 부가적으로, 소셜 네트워크의 사용자들은 자신의 관심에 대한 설명을 작성하고, 이야기를 구성하며, 자신의 삶을 묘사하는 것 등이 가능하다. 일부 사용자들은 대량의 컨텐츠를 생성할 수 있는 반면에, 다른 사용자들은 매우 적게 생성할 수 있다.

일반적으로, 본 문서는 사용자의 관심을 추론하는 것을 기술한다.

일반적인 제 1 측면의 경우, 컴퓨터로 구현되는 방법이 기술된다. 본 방법은 소셜 네트워크의 사용자에 의하여 생성된 컨텐츠에 기초하여 컨텐츠 기반의 키워드를 생성하는 단계를 포함한다. 본 방법은 광고주에 의해 지정된 하나 이상의 용어에 기초하는 광고주 선택형 키워드와 일치하는 컨텐츠 기반 키워드를 포함하는 광고 라벨로, 사용자의 표시인 사용자 노드를 포함하는 노드를 라벨링하는 단계를 포함한다. 본 방법은 또한 각각의 노드에 대하여, 관계에 의해 상기 노드에 관련된 이웃하는 노드와 연관된 광고 라벨의 가중치에 기초하여 상기 광고 라벨에 대한 가중치를 출력하는 단계를 포함한다.

일반적인 제 2 측면의 경우, 컴퓨터로 구현되는 방법이 기술되며, 여기서 본 방법은 디스플레이하기 위한 온라인 광고를 선택하는데 사용하기 위하여 광고주에 의해 지정된 용어에 기초하여 선택된 키워드를 수신하는 단계를 포함한다. 본 방법은 또한 소셜 네트워크의 사용자를 대표하는 사용자 노드 중 일부를 상기 선택된 키워드로 라벨링하는 단계; 및 각각의 사용자 노드에 대하여, 소셜 관계에 의해 상기 사용자 노드에 관련되는 이웃하는 사용자 노드와 연관된 선택된 키워드의 가중치에 기초하여 상기 선택된 키워드에 대한 가중치를 출력하는 단계를 포함한다.

일반적인 제 3 측면의 경우, 시스템이 기술된다. 본 시스템은 소셜 네트워크의 사용자의 표시를 포함하는 노드를 상기 사용자에 의해 생성된 컨텐츠로부터 얻어진 컨텐츠 키워드를 포함하는 광고 라벨로 라벨링하기 위한 분류 모듈을 구비한다. 상기 광고 라벨은 광고주에 의해 지정된 하나 이상의 용어에 기초하는 광고주 선택형 키워드와 일치한다. 본 시스템은 또한 관계에 의하여 상기 노드에 관련되는 이웃하는 노드와 연관된 광고 라벨의 가중치에 기초하여 상기 광고 라벨에 대한 가중치를 출력하기 위한 수단을 구비한다.

여기에 기술하는 본 시스템과 기술은 다음의 이점 중 하나 이상을 제공할 수 있다. 첫째, 소셜 네트워크 사용자의 대형 세그먼트(Segment)를 식별하여 정확하게 광고를 위해 타게팅하는 것이 가능하다. 둘째, 사용자 및 사용자의 관심을 자동화된 방식으로 광고주 및 광고주 키워드에 매핑하는 것이 가능하다. 셋째, 컨텐츠는 사용자가 해당 컨텐츠를 생성하지 않은 경우조차 사용자와 연관지어지고 사용자의 관심을 식별하기 위하여 사용될 수 있다. 넷째, 광고주가 선택하지 않은 키워드는 소셜 네트워크 사용자의 타게팅을 용이하게 하기 위하여 광고주 선택형 키워드나 광고주에 (예컨대, 광고 목적으로) 매핑될 수 있다.

하나 이상의 실시형태에 관한 세부사항들은 첨부도면과 이하의 상세한 설명에서 제시된다. 다른 특징과 이점들은 상세한 설명과 도면 및 청구항으로부터 명백해질 것이다.

도 1은 제 1 소셜 네트워크 사용자에 사회적으로 관련되어 있는 다른 사용자의 정보에 기초하여 제 1 소셜 네트워크 사용자에 대한 정보를 추론하기 위한 예시적인 시스템의 개략도.

도 2는 소셜 네트워크 시스템에 의하여 제공되는 사용자 프로필에 대한 라벨을 추론하는 서버 시스템을 나타내는 예시적인 시스템의 블록도.

도 3은 추론된 라벨을 생성하기 위한 예시적인 방법.

도 4a 내지 4d는 사용자 및 사용자의 그룹을 라벨링하기 위해 사용되는 예시적인 정보를 나타내는 도면.

도 5는 이웃하는 노드의 라벨에 기초하여 라벨을 추론하기 위한 예시적인 방법을 나타내는 도면.

도 6a 내지 6e는 알고리즘이 사용자에 대한 라벨값을 추론하기 위해 사용되는 경우에 소셜 네트워크의 사용자들의 예시적인 그래프를 나타내는 도면.

도 7은 사용자 관심을 추론하는데 사용하기 위한 선택적인 예제 그래프.

도 8은 광고주가 선택한 용어의 그룹을 포함하는 노드를 갖는 선택적인 예제 그래프.

도 9a 내지 9c는 그래프 내의 노드에 대한 라벨을 추론하기 위하여 사용되는 부가적인 노드를 포함하는 선택적인 예제 그래프.

도 10은 모든 키워드가 라벨로서 사용되는 경우의 그래프.

도 11은 광고주가 라벨로서 사용되는 경우의 그래프.

도 12는 사용자가 라벨로서 사용되는 경우의 그래프.

도 13은 더미(Dummy) 노드를 포함하는 그래프.

도 14는 컴퓨터 시스템(1400)의 개략도.

여러 도면에서 동일한 참조기호는 동일한 요소를 나타낸다.

본 문서는 사용자의 관심을 추론하기 위한 시스템 및 기술을 설명한다. 소셜 네트워크는 그 소셜 네트워크의 사용자에 의하여 생성된 사용자 정보를 호스트할 수 있다. 예컨대, 도 1에 나타낸 바와 같이, 사용자는 프로필(102)을 생성할 수 있으며, 이는 관심, 이야기, 사실, 혹은 사용자에 관한 묘사를 포함할 수 있다. 부가적으로, 사용자는 다른 사용자와의 사회적인(Social, 소셜) 관계를 지정할 수 있다. 예컨대, 사용자는 "친구"인 다른 사용자를 지정할 수 있다.

도 1의 서버 시스템(104)과 같은 광고 시스템은 소셜 네트워크 상에서 제공되는 사용자 프로필을 열람하는 사람에게 온라인 광고(Advertisements, Ads)를 타 게팅(Targeting)할 수 있다. 특정한 구현예의 경우, 광고 시스템은 프로필의 내용에 기초하여 온라인 광고를 생성한다. 일부의 경우, 사용자는 자신의 프로필에 충분한 정보를 제공하지 못하거나 전혀 못할 수 있는데, 이는 해당 프로필에 대하여 정확하게 타게팅되는 온라인 광고를 생성하기 어렵게 만들 수 있다.

제 1 사용자의 프로필 정보가 부족한 경우에, 그 제 1 사용자와 관련된 다른 사용자들의 프로필을 사용하여 제 1 사용자의 프로필과 함께 디스플레이할 온라인 광고를 생성하는 것이 가능하다. 예를 들어, 제 1 사용자인 Isaac은 Jacob과 Esau 2명의 친구를 가진다는 점을 제외하고는 자신의 프로필에 아무런 정보를 갖고 있지 않을 수 있다. 본 서버 시스템(104)은 Isaac의 프로필에 대한 정보를 추론하기 위하여 Jacob과 Esau의 프로필로부터의 정보를 사용할 수 있다. 이 추론된 정보는 Isaac의 프로필이 열람될 때 표시되는 온라인 광고를 생성하는데 이용될 수 있다.

다른 경우에 있어서, 소셜 네트워크 사용자에 대한 프로필은 광고주가 자신의 캠페인을 타게팅하기 위해 사용하는 키워드에 대응하지 않는 용어나 구어(Colloquialism)를 포함할 수 있다. 이들 용어나 구어는 해당 용어나 구어(집합적으로 비광고 키워드라고 지칭함)와 키워드 간의 관계를 추론함으로써 광고주에 의해 사용되는 키워드에 매핑하는 것이 가능하다.

일부 구현예의 경우, 상기 비광고 키워드와 광고 키워드 간의 추론된 관계는 사용자 프로필에서 지정된 소셜 관계에 기초한다. 예컨대, Jacob은 자신의 프로필에 "hax0r"(즉, 해커)와 "btch"(즉, Chuck Norris보다는 낫다) 등의 용어를 포함할 수 있는데, 이것은 광고 키워드에 매칭되지 않는다. Jacob의 프로필은 Leah와 Rachel이 친구임을 지정하고 있다. Leah와 Rachel 모두 자신의 프로필에 "Ajax"(즉, 비동기식 JavaScript 및 XML)와 Perl(Practical Extraction and Reporting Language) 등의 용어를 포함하고 있고, 이것은 광고 키워드에 대응한다. 서버 시스템(140)과 같은 광고 시스템은 Leah 및 Rachel의 용어와 Jacob의 용어 간 관계를 생성하는데 사용될 수 있으며, 이로써 Leah와 Rachel에 대해 자신의 프로필의 키워드에 기초하여 타게팅된 광고가 Jacob에 대한 광고를 타게팅하는데에도 사용 가능하며, 이는 Leah와 Rachel의 프로필에 있는 용어와 Jacob의 프로필 간에 관계(Association)가 추론되었기 때문이다.

도 1은 제 1 소셜 네트워크 사용자에 사회적으로 관련되어 있는 다른 사용자의 정보에 기초하여 제 1 소셜 네트워크 사용자에 대한 정보를 추론하기 위한 예시적인 시스템(100)의 개략도이다. 일부 구현예의 경우, 본 시스템은 소셜 네트워크 시스템(106)과 이전에 논의한 서버 시스템을 포함하며, 이는 프로필에 의하여 지정된 소셜 관계에 기초하여 개별적인 사용자의 프로필 내 정보 간의 관계를 결정할 수 있다.

일부 구현예에서, 소셜 네트워크 시스템(106)은 사용자 프로필(102)을 포함하며, 이는 사용자의 관심, 사용자 블로그, 자신 혹은 다른 사용자의 프로필에 대한 해당 사용자의 포스팅(Posting)(예컨대, 웹 페이지의 말쓰기 영역에 있는 코멘트), 호스트되는 오디오, 이미지 및 기타 파일에 대한 사용자의 선택 및 사용자에 관한 나이, 성별, 주소 등의 인구통계학적인 정보 등 사용자가 생성한 컨텐츠를 포함할 수 있다.

부가적으로, 프로필(102)은 소셜 네트워크 시스템(106)의 사용자들 간의 관계를 지정하는 소셜 관계를 포함할 수 있다. 예컨대, 사용자인 Joshua는 Aaron과 Caleb를 친구로 나열할 수 있으며, 제 2 회원으로서 Izzy를 포함하는 Trumpet Player Society(트럼펫 연주자 모임)의 회원일 수 있다. 상기 지정된 친구 관계와 그룹 멤버쉽 관계는 사용자인 Joshua, Aaron, Caleb 및 Izzy 간 사용자 관심의 유사성을 추론하는데 사용 가능하다.

프로필(102)의 정보 내지 컨텐츠(108)는 화살표(110)로 나타낸 바와 같이 서버 시스템(104)으로 전송될 수 있다. 이 서버 시스템(104)은 관련된 사용자 프로필(예컨대, 같은 그룹이나 클럽, 모임의 회원이거나 친구인 프로필 등)의 내용에 기초하여 불완전하거나 부족하게 채워진 사용자 프로필에 대한 라벨을 생성하기 위해 추론된 라벨 생성기(111)를 사용할 수 있다.

일부 구현예의 경우, 라벨은 프로필에 관련된 키워드를 포함할 수 있다. 예를 들어, 라벨은 웹 페이지 프로필에 포함되는 자동차 등의 키워드일 수 있다. 다른 구현예의 경우, 라벨은 프로필의 내용에 관련된 카테고리일 수 있는데, 예를 들면 프로필은 Corvettes(콜벳), Vipers(바이퍼) 및 Hugos(휴고)를 기술하는 컨텐츠를 포함할 수 있다. 프로필에 적용된 라벨은 Corvettes, Viper 및 Hugo 용어와 카테고리 "자동차" 간의 미리 정해진 관계에 기초하여 "자동차"가 될 수 있다.

도 1의 구현예에서, 서버 시스템(104)은 데이터 저장부(112)를 포함하고, 여기에서 라벨에 관한 정보가 저장될 수 있다. 일부 구현예의 경우, 각각의 사용자 프로필은 하나보다 많은 라벨과 연관지어질 수 있다. 각각의 프로파일 및 대응하는 라벨 간의 관계는 라벨값 테이블(114)과 같은 데이터 구조에 저장될 수 있다.

일부 구현예의 경우, 라벨값 테이블(114)은 각 라벨에 대한 가능한 관심 레벨을 나타내는 라벨값을 포함할 수도 있다. 예를 들어, Adam의 프로필은 정원 가꾸기와 축산에 관한 내용을 포함할 수 있지만, 2배의 내용이 정원 가꾸기에 집중될 수 있다. 라벨값 테이블(114)은 Adam의 프로필 엔트리 하에서 축산에 대해서는 0.33을, 정원 가꾸기에 대해서는 0.66의 라벨값을 포함할 수 있으며, 이는 상기 프로필이 축산보다 2배 많은 정원 가꾸기에 관한 정보를 포함한다는 점을 나타낸다.

데이터 저장부(112)는 또한 소셜 네트워크 시스템(106)에 의하여 호스트되는 프로필을 지향하는 온라인 광고(120)를 생성하는데 사용되는 광고 정보(116)를 포함할 수 있다. 온라인 광고(120)는 서버 시스템(104)에 의하여 호스트되는 광고 서버(118)에 의해 전송 가능하다. 광고 서버(118)는 사용자 프로필에 연관된 라벨에 기초하여 사용자 프로필에 대하여 타게팅된 온라인 광고(120)를 생성하기 위해 라벨값 테이블(114)의 라벨 정보를 사용할 수 있다. 서버 시스템(104)은 화살표 122로 나타낸 바와 같이 사용자 프로필이나 그 사용자 프로필과 연계된 사용자들과 함께 디스플레이하기 위해 타겟 광고(120)를 소셜 네트워크 시스템(106)으로 전송할 수 있다.

도 2는 소셜 네트워크 시스템에 의하여 제공되는 사용자 프로필에 대한 라벨을 추론하는 서버 시스템(202)을 나타내는 예시적인 시스템(200)의 블록도이다. 상기 서버 시스템(202)은 추론된 라벨 생성기(204), 라벨과 광고 정보를 저장하는 제 1 데이터 저장부(206), 미리 정해진 라벨(210)을 포함하는 제 2 데이터 저장 부(208) 및 광고 서버(212)를 포함한다.

일부 구현예의 경우, 서버 시스템(202)은 화살표(216)로 나타낸 바와 같이 소셜 네트워크 시스템으로부터 사용자 프로필의 컨텐츠(214)를 수신할 수 있다. 이 서버 시스템은 대응하는 사용자나 사용자 프로필에 타게팅되는 온라인 광고(218)를 생성하거나 식별하기 위하여 라벨이 사용 가능한 경우에, 컨텐츠(214)에 기초하여 라벨을 식별하거나 생성하기 위해 컨텐츠(214)를 사용할 수 있다.

일부 구현예의 경우, 상기 추론된 라벨 생성기(204)는 라벨을 추론하기 위하여 사용되는 데이터 구조를 생성하도록 데이터 구조 생성기(220)를 포함한다. 예컨대, 데이터 구조 생성기는 각 사용자(혹은 사용자 프로필)가 노드로 대표되는 그래프를 생성할 수 있다. 데이터 구조 생성기(220)는 사용자에 의해 지정된 소셜 관계에 기초하여 에지(Edge)를 갖는 노드를 링크하는 관계 결정 모듈(222)을 포함할 수 있다. 예를 들어, 사용자 Adam은 Seth가 친구임을 자신의 프로필에 지정할 수 있다. 관계 결정 모듈(222)은 Adam과 Seth에 대한 사용자 노드를 에지와 결합시킬 수 있다. 에지는 양방향 혹은 단방향일 수 있으나, 명료성을 위하여 이하의 예에서는 따로 정하지 않는 한 양방향인 것으로 한다.

상기 추론된 라벨 생성기(204)는 분류 모듈(224)을 포함할 수도 있으며, 이는 소셜 네트워크 시스템의 사용자들을 제 2 데이터 저장부(208)의 미리 정해진 라벨(210)과 같은 라벨과 연관지을 수 있다. 예컨대, 분류 모듈은 Yang, Yiming 및 Pedersen, Jan O.저 "A Comparative Study on Feature Selection in Text Categorization Source"에 기술된 것과 같은 텍스트 분석 기법을 사용할 수 있다. 기계 학습에 관한 제4차 국제 컨퍼런스 회의록의 페이지 412-420, Sebastiani Fabrizio ACM Computing Surveys(CSUR) 아카이브 34권 1판 (2002년 3월) "Machine learning in automated text categorization" 페이지 1-47 및 Joachims, Thorsten 컴퓨터 과학 강의 노트 1398권 아카이브 "Text Categorization with Suport Vector Machines: Learning with Many Relevant Features", 기계 학습에 관한 제10차 유럽 컨퍼런스 회의록 페이지 137-142는 여기에 그 전부가 참고로 편입된다. 텍스트 분석은 생성된 그래프에서 사용자 노드와 연관지식 위하여 라벨을 결정하는데 사용 가능하다. 이러한 분석의 대상은 사용자 프로필, 사용자에 의해 포스트된 코멘트, 사용자가 속하는 그룹의 설명 등을 포함할 수 있다. 다른 구현예에서, 미리 정해진 라벨(210)은 키워드(231)에 기초할 수 있으며, 이는 광고주에 의해 제시된다. 예컨대 키워드(231)는 "furniture(가구)"라는 용어를 포함할 수 있다. 이것은 미리 정해진 라벨로서 사용 가능하며, 분류 모듈(224)은 이를 "furniture"라는 용어를 포함하는 프로필을 갖는 사용자와 연관짓는다. 부가적으로, 분류 모듈은 만약 사용자 프로필이 의자, 테이블이나 가정용 장식품 등의 "furniture(가구)"와 연관된 단어를 포함한다면, "furniture"라는 라벨과 해당 사용자를 연관지을 수 있다.

일부 구현예에서, 상기 추론된 라벨 생성기(220)는 라벨값 수정 모듈(226)도 포함한다. 라벨값 수정 모듈(226)은 이하에서 더욱 상세하게 설명하는 방법 및 구조를 이용하여 사용자와 연계된 라벨값(그리고 사용자의 그룹, 광고주가 선택한 키워드, 키워드 그룹, 광고주 및 광고주가 선택하지 않은 키워드와 관련된 라벨값)을 수정할 수 있다.

초기 및 수정된 라벨값은 일부 구현예에 있어서 제 1 데이터 저장부(206)의 라벨값 테이블(228)과 같은 데이터 구조에 저장될 수 있다. 도 2에 나타낸 바와 같이, 라벨값 테이블(228)은 다음의 사용자, 사용자의 그룹, 광고주가 선택하지 않은 키워드 및 광고주가 선택한 키워드의 그룹 각각과 라벨값을 연관짓는 인덱스(Index)를 포함할 수 있다.

광고 서버(212)는 각 사용자와 연관된 라벨값 혹은 복수의 라벨값에 기초하는 전자 광고를 생성하거나 선택하기 위하여 상기 제 1 데이터 저장부에 저장된 광고 정보를 이용할 수 있다. 이 광고 정보는 예컨대 광고주가 자신의 광고와 연관짓도록 선택한 키워드(231)를 포함할 수 있다. 광고 정보는 또한 키워드 중 하나가 예컨대 사용자의 프로필에서 발생하는 경우에 디스플레이할 광고와 연계되고 관련 키워드를 포함하는 카테고리인 광고 단어 그룹(234, 애드그룹(Adgroup, 광고 그룹)이라고도 지칭함)을 지정할 수도 있다. 부가적으로, 광고 정보(230)는 식별자, 정산 정보, 광고에 대한 입찰가 등 광고주에 관한 정보(236)를 포함할 수 있다.

도 3은 추론된 라벨을 생성하기 위한 예시적인 방법(300)이다. 일 구현예에서, 본 방법(300)은 서버 시스템(202)의 프로세서에 의해 실행되고 명령어로서 구현 가능한 스텝들을 포함한다.

본 방법(300)은 스텝 302로 시작할 수 있으며, 여기서는 사용자와 연관짓기 위한 라벨이 선택된다. 예컨대, 라벨은 관심(예컨대, 음악, 영화, 사업 등)과 키워드("Britney Spears(브리트니 스피어스)", "tables(테이블)", "masks(마스크)" 등)의 양쪽 카테고리를 모두 포함할 수 있다. 일부 구현예의 경우, 카테고리나 키워드 중 하나가 라벨로서 선택된다. 또한, 카테고리나 키워드의 하위 세트가 라벨로서 사용하기 위하여 상위 세트로부터 선택될 수 있다. 예를 들어, 사용자는 추론된 라벨 생성기(204)에 특정한 키워드의 선택을 입력할 수 있으며, 이 경우 상기 선택은 추론된 라벨 생성기(204)가 카테고리인 "Racing(레이싱)", "Stocks(주식)", "music(음악)", "politics(정치학)" 및 "religion(종교)"를 키워드로서 사용해야 함을 지정한다.

스텝 304에서, 스텝 203에서 선택된 라벨은 사용자와 연계된 전자 문서의 내용에 기초하여 사용자에게 할당된다. 예컨대, 분류 모듈(224)은 사용자의 프로필이나 사용자가 생성한 다른 내용에 기초하여 각 사용자를 분류할 수 있다. 분류 모듈(224)은 분류를 달성하기 위하여 텍스트-분류 기계 학습 알고리즘을 사용할 수 있다. 특정한 구현예에서, 사용자는 하나보다 많은 라벨을 사용하여 분류될 수 있다. 부가적으로, 일부 구현예의 경우 만약 사용자의 프로필이 분류하기에 충분한 정보를 갖지 않는다면, 그 사용자는 미분류로 남겨진다.

방법(300)에 도시하지는 않았으나, 일부 구현예의 경우 만약 소셜 네트워크 시스템이 클럽, 모임, 클래스 등 어떠한 사용자 그룹이라도 포함한다면, 분류 모듈(224)은 해당 그룹을 기술하거나 그 그룹의 메세지 보드 등 그 그룹과 연계된 텍스트 및 기타 컨텐츠에 기초하여 해당 그룹을 분류하려고 시도할 수 있다. 분류 모듈은 사용자 분류가 이루어진 것과 실질적으로 동일한 방식으로 그룹을 분류할 수 있다.

스텝 306에서, 그래프 등의 데이터 구조가 생성된다. 예컨대, 데이터 구조 생성기(220)는 각각의 사용자, 사용자 그룹, 미선택된 키워드나 카테고리, 광고 그룹 및 광고주를 그래프의 노드로서 나타낼 수 있다. 관계 결정 모듈(222)은 상기 노드에 의하여 지정된 소셜 및 기타 관계에 기초하여 상기 노드들을 링크시킬 수 있다. 예를 들어, 상기 관계 결정 모듈(222)은 만약 사용자들이 서로 "friends(친구)"라고 자신들의 사용자 프로필에 지정하였다면 그 2개의 사용자 노드를 함께 링크시킬 수 있다. 다른 예에서, 광고주 노드는 광고주에 의해 지정되었던 키워드를 포함하는 광고 그룹에 링크될 수 있다.

일부 구현예의 경우, 서로 다른 라벨에 대하여 복수의 라벨값을 갖는 라벨 노드 또한 사용자 노드와 연관지어진다. 이러한 라벨 노드는 사용자 노드 속으로 라벨값을 "주입(Inject)"한다(예컨대, 도 6a 참조). 이 점에 대해서는 도 4 내지 13과 관련된 더 자세한 설명에서 다룬다.

부가적으로, 일부 구현예의 경우 상기 추론된 라벨 생성기(204)는 제 2 그래프와 같은 제 2 데이터 구조를 생성한다. 상기 제 2 그래프는 또한 관심 있는 단일 주제를 표현하는 하나 이상의 라벨 노드와 각 사용자가 연관지어질 수 있다는 점을 제외하고는(예컨대, 도 7 참조) 상기 제 1 그래프와 실질적으로 동일한 노드를 포함할 수도 있다.

스텝 308에서, 사용자가 선택된다. 예컨대, 상기 추론된 라벨 생성기(204)는 그래프에서 사용자를 대표하는 사용자 노드를 선택할 수 있다. 추론된 라벨 생성기(204)는 선택된 사용자 노드에 링크되어 있는 이웃하는 사용자 노드(예컨대, 사용자의 친구)에 액세스하여, 그 라벨값을 이용해서 스텝 310에서 나타낸 바와 같이 선택된 사용자에 대한 신규 혹은 수정된 라벨값을 생성하는 것이 가능하다.

만약 선택된 사용자가 신규 혹은 수정된 라벨값을 할당받지 않은 부가적인 라벨을 가지고 있다면, 상기 추론된 라벨 생성기는 모든 라벨이 처리될 때까지 스텝 312에 나타낸 바와 같이 추가 라벨을 선택해서 스텝 310을 반복한다.

스텝 314에서, 사용자에 대한 라벨값들이 표준화된다. 예컨대, 추론된 라벨 생성기(204)는 0과 1 사이의 숫자로 라벨값을 표준화할 수 있으며, 이 경우 상기 숫자는 다른 라벨값의 기여분에 대하여 상대적인 해당 라벨값의 기여분을 나타낸다. 예를 들어, 만약 미리 표준화된 라벨값이 Stocks=2.0, Racing=1.0, 그리고 Gambling=1.0이라면, 표준화된 값은 Stocks=0.5, Racing=0.25, 그리고 Gambling=0.25가 될 것이다.

만약 본 방법(300)을 이용하여 선택되지 않은 추가적인 사용자들이 존재한다면, 다음의 미선택 사용자가 스텝 316에 나타낸 바와 같이 선택될 수 있다. 예를 들어, 추론된 라벨 생성기(204)는 다음의 미선택 사용자 노드를 선택할 수 있다. 모든 사용자가 선택된 경우에는, 본 방법(300)이 종료될 수 있다.

일부 구현예에서, 스텝 308 내지 316은 스텝 306과 관련하여 기술한 제 2 그래프 상에서 수행될 수도 있다. 추론된 라벨 생성기(204)는 제 1 및 제 2 그래프 양쪽으로부터 대응하는 사용자 노드에 대한 결과적인 라벨값 크기를 선택해서 비교할 수 있다. 일부 구현예의 경우, 상기 추론된 라벨 생성기(204)는 최종적인 라벨값 크기를 결정하기 위하여 선형 가중을 통해 각 그래프로부터의 라벨값 크기를 결합할 수 있다(예컨대, 제 1 그래프의 라벨값은 0.7을 기여하고, 제 2 그래프의 라 벨값은 0.3을 기여함). 다른 구현예의 경우, 최종 라벨값을 결정하기 위하여 값들을 균등하게 가중하거나(예컨대, 0.5, 0.5), 상기 추론된 라벨 생성기(204)가 다른 그래프로부터의 값을 무시하면서 그 전체적인 기여분에 하나의 값을 제공할 수도 있다(예컨대, [1.0, 0.0] 혹은 [0.0, 1.0]).

다른 구현예의 경우, 추론된 라벨 생성기는 각 그래프로부터의 라벨값 크기에 대한 기여분 가중을 설정하기 위하여 상호 검증(Cross-Validation) 기법을 사용할 수 있다. 예를 들어, 추론된 라벨 생성기(204)는 그래프의 사용자 노드에 액세스할 수 있으며, 여기서 사용자 노드는 알려진 라벨값 크기를 갖는다. 추론된 라벨 새성기(204)는 상기 알려진 라벨값 크기와 실제 라벨값 크기를 비교할 수 있다. 그러면 추론된 라벨 생성기(204)는 그 값이 알려진 라벨값에 얼마나 근사하게 부합하는지에 기초하여 각각의 그래프를 가중하는 것이 가능하다.

특정한 구현예에서, 라벨 생성기(204)는 최종 라벨 크기를 검증하는 것에 대신하거나 그것에 부가하여, 예상되는 선험적(A Priori) 분포에 상기 라벨값 크기를 비교할 수 있다. 예컨대, 만약 모든 라벨 노드에 걸친 label_A의 합계 가중이 8.0이고 모든 라벨 노드에 걸친 label_B의 가중치가 4.0인 경우에, 선험적인 분포는 label_A가 label_B보다 2배 더 일어날 확률이 있음을 제시한다. 추론된 라벨 생성기(204)는 각각의 사용자 노드에 대한 라벨값 크기를 조정하기 위하여 이러한 예상을 사용할 수 있다. 만약 node_n에서 Label_A 가중치가 1.5이고 label_B 가중치가 1.0이라면, label_A에 대한 증거는 label_B보다 더 높음에도 불구하고 기대한 만큼은 높지 않은데, 그 이유는 상기 비율이 선험적 분포만큼 높지 않기 때문이다. 이 는 크기에 있어서의 차이가 의미있다는 신뢰성을 떨어뜨린다. 신뢰 계수는 랭킹으로 다시 변환될 수 있다.

일부 구현예에서, 만약 크기의 차이가 신뢰 임계값 이하라면, 추론된 라벨 생성기(204)는 더 작은 가중치를 갖는 라벨을 더 높은 가중치를 갖는 라벨보다 위에 랭크할 수 있다(예컨대, 더 낮은 가중치를 조정하여, 더 높은 가중치보다 더 높은 값으로 상승하게끔 한다). 예컨대, label_A의 가중치가 label_B의 가중치의 3배로 기대되지만 label_B보다 단지 1.1배 더 큰 경우를 가정하면, 추론된 라벨 생성기(204)는 label_B를 label_A보다 위에 랭크할 수 있다. 일부 구현예의 경우, 신뢰 계수는 신뢰도(Confidence Measure)로서 관리될 수 있으며, 이는 예컨대 결과적인 라벨값 크기를 가중하기 위한 기계 학습 알고리즘에 의해 사용 가능하다.

또 다른 구현예의 경우, 라벨 노드의 선험적 분포에 기초하여 라벨값 크기를 비교하는 것 대신에 혹은 그것에 부가하여, 추론된 라벨 생성기(204)가 모든 노드에 걸친 크기의 최종 분포에 기초하여 라벨값 크기를 비교할 수 있다. 예컨대, 추론된 라벨 생성기(204)는 특정한 노드의 분포가 그래프 상 모든 노드에 걸쳐서 연산된 평균과 얼마나 차이가 나는지를 측정할 수 있다.

일부 구현예의 경우, 라벨이 추론된 라벨 생성기(204)에 의하여 생성되었다면, 광고 서버(212)가 그 라벨을 이용하여 디스플레이할 광고를 선택할 수 있다. 예컨대, 만약 사용자 노드가 Britney Spears" 라벨과 연관되어 있다면, 광고 서버(212)는 그 사용자 노드와 연관된 사용자 프로필과 함께 디스플레이할 음악 광고를 선택할 수 있다. 다른 예에서, 만약 라벨이 "religion"이라면, 광고 서버(212) 는 종교에 관련된 용어의 등장에 기초하여 표시되도록 광고주가 지정한 광고나 종교적이라고 결정된 광고를 선택할 수 있다.

또 다른 구현예의 경우, 다른 인자가 라벨에 기초하여 광고가 디스플레이될지 여부에 영향을 미칠 수 있다. 예컨대, 광고 서버(212)는 광고주가 노출/클릭/거래/기타 당 비용과 같이 광고의 디스플레이에 대하여 얼마나 지불할 의사가 있는지를 산입하여, 광고를 디스플레이할지 여부 및 어느 광고를 디스플레이할 것인지를 결정할 수 있다.

도 4a 내지 4b는 사용자 및 사용자의 그룹을 라벨링하기 위해 사용되는 예시적인 정보를 나타내는 도면이다. 도 4a에 도시한 예제 테이블(400)은 소셜 네트워크의 사용자들에 관한 정보를 포함하고 있다. 예제 테이블(400)은 4개의 열을 포함하며, 이들은 회원 식별자(402), 사용자의 친구를 지정하는 식별자(404), 사용자의 프로필 페이지(406)로부터의 내용에 기초하여 생성된 초기 라벨(406) 및 사용자가 어떤 그룹과 연계되어 있는지를 지정하는 식별자(408)를 포함한다.

도 4b는 예컨대 소셜 네트워크 상의 그룹의 프로필 페이지로부터의 내용과 같이 그룹을 기술하는 내용에 기초하여 생성된 초기 라벨(414)과 소셜 네트워크 시스템의 그룹에 대한 식별자(412)를 포함하는 예제 테이블(410)을 나타낸다. 특정한 구현예에서, 이 라벨은 전술한 바와 같은 텍스트 분석 기법을 이용하여 분류 모듈(224)에 의해 테이블에서 생성 및 저장될 수 있다.

이러한 정보는 도 4c에 나타낸 예시적인 그래프 데이터 구조(416)에 의해서도 나타내어질 수 있다. 소셜 네트워크의 사용자 각각은 그래프에서 노드로서 나타 내어질 수 있다. 예컨대, Abby, Bob, Cal, Dale 및 Ernie는 각각 노드(418, 420, 422, 424 및 426)으로 나타내어져 있다. 간단한 설명을 위해, 그래프 데이터 구조(416)는 도 4b의 테이블에 포함된 VeganVets4Life 및 CannotDrive55와 같은 그룹과 연계된 노드를 명시적으로 나타내고 있지는 않다. 그러나, 그룹과 연계된 라벨(예컨대, Recycled Tofu, Dogs 및 NASCAR)은 그룹의 회원과 연관지어져 있다. 이는 이하에서 더욱 자세하게 설명한다.

특정한 구현예에서, 사용자 노드는 사용자에 의해 지정된 소셜 관계에 기초하여 에지에 의해 링크된다. 예컨대, Abby 노드(418)는 에지(419)에 의하여 Cal 노드(422)에 링크되어 있는데, 이는 Abby가 자신의 프로필 페이지에서 Cal이 친구임을 지정하였기 때문이다. 도 4c는 또한 사용자의 가능성 있는 관심을 표현하는 라벨과 사용자 노드를 연관짓는 라벨 노드를 나타내고 있다. 일부 구현예의 경우, 상기 라벨 노드는 이웃하는 노드의 라벨값에 기초하여 변경되지 않을 수 있는 라벨값을 갖는다. 이는 본 도면에서 단방향 에지(429)에 의하여 도시되어 있다.

예컨대, Abby 노드(418)는 라벨 Dogs에 대해 라벨값 0.66을 가지고 라벨 Recycled Tofu(도 4c에서는 Tofu로 축약함)에 대해 0.33을 갖는 라벨 노드(428)와 연계되어 있다. 특정한 구현예에서, 라벨들은 각각의 라벨이 사용자 노드에 얼마나 많이 기여하였는지를 나타내는 라벨값을 갖는다. 라벨 Dogs는 Abby가 Dogs에 관심이 있다는 점을 Abby의 프로필 페이지의 내용에 기초하여 지정하고 있다. Dogs에 대한 라벨값은 Abby가 그룹 VeganVets4Life의 회원이기 때문에 상승하게 되는데, 이 역시 라벨 Dogs와 연계되어 있다. Abby가 VeganVets4Life의 회원이기 때문에, Abby 노드(418)는 Recycled Tofu에 대한 라벨값과도 연관지어져 있다.

이 예에서, Dogs에 대한 라벨값은 Recycled Tofu에 대한 값의 2배인데, 이는 Abby가 2가지 수단(Abby 프로필의 내용은 물론이고 VeganVets4Life의 그룹 멤버쉽)을 통해 Dogs 라벨과 연관된 반면에, Recycled Tofu와는 1가지 소스(예컨대, VeganVets4Life의 그룹 멤버쉽)를 통해서만 연관되어 있기 때문이다.

Bob 노드(420)는 라벨 노드(430)와 연관되어 있으며, 이는 Bob이 예컨대 Bob의 프로필에 기초하여 Racing과 Stocks에 균등한 관심을 가지고 있다는 점을 나타낸다.

라벨 노드(432)는 Ernie 노드(426)와 연관되어 있으며, Ernie가 Stocks, Gambling 및 NASCAR에 관심이 있음을 나타낸다. 더욱 상세하게는, 라벨값은 Ernie가 이들 3가지에 전부 균등하게 관심이 있음을 나타낸다. 이 예에서, Stocks와 Gambling 라벨은 Ernie의 프로필로부터 얻어진 것이고, NASCAR 라벨은 도 4a의 테이블로 나타낸 바와 같이 그룹 CannotDrive55의 Ernie의 멤버쉽으로부터 얻어진 것이다. 이 예에서, 라벨값은 0과 1 사이의 값에 표준화되어 있으며, 여기서 라벨의 기여분은 모든 라벨에 비례한다. Ernie가 Gambling, Stocks 및 NASCAR에 균등한 관심을 가지고 있으므로, 각각은 0.33의 라벨값을 할당받는다.

도 4d는 도 4a 및 4b에 도시한 정보에 대한 예시적인 그래프 데이터 구조(440)의 다른 구현예를 나타낸다. 여기서 각 사용자 노드는 가변 라벨 노드(442)와 연관되어 있으며, 이는 이웃하는 노드의 라벨값에 기초하여 수정 가능한 라벨값들을 포함할 수 있다. 여기서, 가변 라벨 노드는 또한 단일의 라벨값을 지정하는 " 고정된" 라벨 노드(444)와 연관지어져 있다. 도 4d에 나타낸 바와 같이, 사용자 노드는 하나보다 많은 가변 라벨 노드와 연관지어질 수 있다.

그룹의 사용자 멤버쉽에 기초하여 사용자에게 에지에 의하여 링크되는 그룹 노드(446)가 도 4c에 부가적으로 도시도어 있다. 그룹 노드는 라벨 노드에 링크되어 있는데, 여기서 예컨대 분류 모듈(224)은 해당 그룹에 대한 텍스트 묘사에 기초하여 라벨 노드에 그 그룹을 링크시킨다.

도 5는 이웃하는 노드의 라벨에 기초하여 라벨을 추론하기 위한 예시적인 방법(500)을 나타낸다. 일부 구현예의 경우, 추론된 라벨 생성기(111 혹은 220)는 서버 시스템(104)의 프로세서에 의하여 실행되는 명령을 포함할 수 있다.

본 방법(500)은 도 4c 및 4d에 나타낸 그래프로부터의 정보를 이용하여 실행될 수 있으며, 그래프의 모든 노드에 대하여 실행 가능하다. 본 방법(500)은 스텝 502에서 출발할 수 있는데, 여기서는 정해진 수의 반복이 그래프에 대하여 실행되었는지 여부가 결정된다. 만약 그 수가 완성되지 않았다면, 스텝 504가 수행된다. 스텝 504에서, 노드가 선택된다. 예컨대, 추론된 라벨 생성기(220)는 사용자 노드, 가변 라벨 노드, 그룹 노드 등 알고리즘에 의하여 수정 가능한 라벨값을 갖는 노드를 선택할 수 있다.

스텝 506에서, 상기 선택된 노드 중에서 라벨이 선택된다. 예를 들어, 추론된 라벨 생성기(220)는 만약 선택된 노드 중에 존재한다면 라벨 "Stocks"를 선택할 수 있다. 스텝 508에서, 선택된 라벨에 대한 라벨값은 0으로 초기화된다. 예를 들어, 추론된 라벨 생성기(220)는 "Stocks"에 대한 라벨값을 0으로 설정할 수 있다.

스텝 510에서, 선택된 노드의 이웃하는 노드가 선택될 수 있다. 예컨대, 선택된 노드는 Abby가 친구임을 지정할 수 있다. 상기 추론된 라벨 생성기(220)는 Abby를 나타내는 이웃하는 사용자 노드를 선택할 수 있다.

스텝 512에서, 선택된 이웃의 대응하는 가중된 라벨값이 선택된 라벨의 라벨값에 더해진다. 예를 들어, Abby가 라벨 "Stocks"에 대하여 라벨값을 가진다면, 추론된 라벨 생성기(220)는 이 값을 "Stocks"에 대하여 선택된 노드의 라벨값에 더한다. 특정한 구현예에서, 이웃 노드로부터 추출된 라벨값은 선택된 노드로부터의 거리의 정도에 기초하여 (예컨대, 이웃하는 노드가 선택된 노드에 직접 링크되어 있는지, 선택된 노드까지 2개의 에지에 의해 링크되어 있는지 여부 등에 기초함) 라벨값의 기여분에 영향을 미치도록 가중될 수 있다. 일부 구현예의 경우, 라벨값은 에지와 관련된 가중치에 기초할 수도 있다. 예컨대, 에지 가중치는 2개 노드 간의 명시적인 관계를 반영할 수 있다. 예를 들어, 제 1 노드는 그 연관된 사용자가 친구 Jack을 좋아한다는 점(Jack의 링크와 연계된 값이 0.8인 경우임)과, 그 사용자가 Jack 만큼이나 친구 Jill을 좋아한다는 점 등을 나타낼 수 있다.

다른 구현예의 경우, 이 기여분은 이웃하는 노드에 대한 링크가 양방향인지 여부(예컨대, 이웃하는 노드가 선택된 노드를 친구로서 역시 지정하고 있음)에 기초하여 가중될 수 있다.

스텝 514에서, 선택할 다른 이웃하는 노드가 존재하는지 여부를 결정한다. 예컨대, 추론된 라벨 생성기(220)는 선택된 노드가 선택되지 않은 어떠한 부가적인 이웃에 대해서 단일의 에지에 의해 링크되어 있지는 않은지 여부를 결정할 수 있 다. 다른 예에서, 사용자는 상기 추론된 라벨 생성기가 이웃을 얼마나 많은 정도로 검색해야 하는지(예컨대, 2개의 에지, 3개의 에지 등에 의해 링크됨)를 지정할 수 있다. 만약 선택되지 않은 다른 이웃이 존재한다면, 스텝 514에 나타낸 바와 같이 스텝 510 및 512가 반복될 수 있다. 만약 다른 이웃이 존재하지 않는다면, 스텝 516이 수행될 수 있다.

스텝 516에서는, 선택된 노드에 다른 라벨이 존재하는지 여부가 결정된다. 예컨대, 선택된 노드는 "Stocks(주식)" 라벨은 물론이고 "business(사업)", "Dogs(개)" 등의 복수의 라벨을 가질 수 있다. 만약 이들 부가적인 라벨이 선택되지 않았다면, 상기 추론된 라벨 생성기(220)는 이전에 선택되지 않은 라벨 중 하나를 선택하여 스텝 506 내지 514를 반복할 수 있다. 만약 노드의 모든 라벨이 선택되었다면, 선택된 노드의 라벨값은 스텝 518에 나타낸 바와 같이 표준화될 수 있다. 예컨대, 추론된 라벨 생성기(220)는 각각의 라벨값을 표준화할 수 있으며, 이로써 그것은 0과 1 사이의 값을 갖게 되고, 여기서 해당 라벨값의 크기는 그 노드에 관련된 라벨값 전부에 대하여 상대적인 기여분에 비례하게 된다.

스텝 520에서, 그래프에서 선택할 추가적인 노드가 존재하는지 여부가 결정될 수 있다. 만약 추가 노드가 존재한다면, 본 방법은 스텝 504로 되돌아갈 수 있다. 만약 그래프의 모든 노드가 선택되었다면, 본 방법은 스텝 502로 되돌아가서 지정된 수의 반복이 해당 그래프에 대해 수행되었는지 여부를 결정할 수 있다. 만약 그렇다면, 본 방법(500)은 종료할 수 있다.

특정한 구현예에서, 본 방법(500)은 다음의 의사 코드(Pseudo Code)를 포함 할 수 있다.

특정한 구현예에서, "x" 반복 이후에 추론된 라벨 생성기는 그래프의 하나 이상의 노드를 검사하고, 라벨의 가중치에 기초하여 각 노드에 라벨을 확률적으로 할당할 수 있다(예컨대, 최대 라벨값을 갖는 라벨이 노드에 할당될 수 있음).

일부 구현예의 경우, 반복의 횟수는 미리 지정된다. 다른 구현예의 경우, 알고리즘은 각 노드에서 라벨에 대한 라벨값이 정상 상태(예컨대, 반복하는 동안의 라벨값 변화의 차이가 지정된 ε보다 작은 상태)에 도달할 때 종료한다.

다른 선택적인 방법의 경우, 사용자 노드에 대한 라벨값은 그래프 상에서 랜덤 워크 알고리즘(Random Walk Algorithm)을 실행함으로써 추론될 수 있다. 더욱 상세하게는, 일부 구현예의 경우 그래프 G가 주어졌을 때 추론된 라벨 생성기(204)는 각 노드로부터 랜덤 워크를 시작함으로써 모든 노드에 대해 라벨값 내지 라벨 가중치를 연산할 수 있다. 랜덤 워크 알고리즘은 만약 에지가 방향성이 있다면 그래프에서 각 에지의 방향을 역으로 하는 경우를 포함할 수 있다. 만약 에지가 양방향이라면, 에지는 변경하지 않은 상태로 둘 수 있다.

추론된 라벨 생성기(204)는 관심 있는 노드를 선택해서 그 노드로부터의 랜덤 워크를 링크된 노드까지 개시할 수 있다. 다중으로 뻗는 노드(예컨대, 복수의 다른 노드에 대한 링크를 갖는 노드)가 존재하는 경우에 각 노드에서, 추론된 라벨 생성기는 따라갈 에지를 임의로 선택할 수 있다. 만약 에지가 가중된다면, 추론된 라벨 생성기는 그 에지의 가중치에 기초하여 에지를 선택할 수 있다(예컨대, 가장 크게 가중된 에지가 처음으로 선택될 수 있음).

랜덤 워크를 하는 동안 라벨링 노드인 노드(예컨대, 다른 노드에 대한 라벨로서 사용됨)가 선택된다면, 이러한 워크에 대한 분류는 그 라벨링 노드와 연관된 라벨이다. 추론된 라벨 생성기는 각각의 분류와 연관된 기록을 관리할 수 있다.

랜덤 워크를 하는 동안 라벨링 노드가 아닌 노드가 선택된다면, 추론된 라벨 생성기는 따라갈 다음의 랜덤한 경로 내지 에지를 선택한다.

추론된 라벨 생성기는 관심 있는 각 노드에 대하여 복수회(예컨대, 1000번 내지 100,000번) 랜덤 워크를 반복할 수 있다. 완료되고 난 이후에, 추론된 라벨 생성기는 라벨의 기록에 기초하여 라벨값을 추출할 수 있다. 이러한 프로세스는 관심 있는 각 노드에 대하여 반복될 수 있다.

도 6a 내지 6e는 알고리즘이 사용자에 대한 라벨값을 추론하기 위해 사용되는 경우에 소셜 네트워크의 사용자들의 예시적인 그래프를 나타낸다. 일부 구현예의 경우, 상기 알고리즘은 상기 방법(500), 상술한 의사 코드 혹은 상술한 랜덤 워크 알고리즘의 일부 혹은 모든 스텝들을 포함할 수 있다. 단순화를 위해, 그래프는 소셜 네트워크의 사용자를 대표하는 노드만을 포함하지만, 그룹, 광고주, 키워드 등 다른 실체 역시 상기 그래프에 표현될 수 있다. 이 점은 이후의 도면과 관련하여 더욱 자세하게 설명한다.

도 6a는 5개의 사용자 노드를 갖는 그래프를 나타내며, 그 각각은 소셜 네트워크 시스템의 사용자를 대표한다. 일부 구현예에서, 분류 모듈(224)은 각 사용자 노드와 연관짓기 위한 키워드를 결정한다. 예컨대, 상기 키워드는 사용자가 속하는 그룹을 기술하는 텍스트로부터, 사용자가 제작한 포스트, 사용자의 프로필 등으로부터 도출될 수 있다.

도 6a의 그래프는 원형의 노드로 표현된 라벨값들이 각각의 사용자 노드에 할당되어 있다는 점을 제외하고는 도 4c에 관하여 설명한 그래프와 유사하다. 그래 프에 대한 라벨은 Dogs, Racing, Stocks 및 Gambling을 포함한다.

첫번째 반복 이후에, 도 6a에 나타낸 바와 같이 Abby 노드(418)는 Dogs=1.0을 포함하는 라벨값(602)을 갖는다. Bob 노드(420)는 Racing=0.5 및 Stocks=0.5를 포함하는 라벨값(604)을 갖는다. Ernie 노드(426)는 Stocks=0.5 및 Gambling=0.5를 포함하는 라벨값(610)을 갖는다. 초기 반복 도중에, 추론된 라벨 생성기는 라벨값(428, 430 및 432)에 기초하여 사용자 노드에 라벨값을 할당한다. 노드에 대하여 언급하지 않은 나머지 라벨값들은 이 예에서 무효(Null)이다.

Cal 노드(422)와 Dale 노드(426) 양자는 무효인 라벨값(606 및 608)을 각각 갖는다. 이는 만약 Cal과 Dale의 사용자 프로필이 분류 모듈(224)에 의한 사용을 위한 정보를 아예 (혹은 충분히) 갖지 않는다면 발생할 수 있으며, 이 경우 사용자 노드에 대해서는 초기의 라벨값을 할당한다.

도 6b는 알고리즘의 두번째 반복 이후에 도 6a의 그래프를 나타낸다. 이 예에서, 사용자 노드는 이웃하는 사용자 노드에 기초하여 할당된 라벨값이다. 예컨대, 상기 추론된 라벨 생성기는 Abby 노드에 기초하여 Dogs에 대한 Cal 노드의 라벨값을 1.0으로 증가시키고, Racing 및 Stocks에 대한 라벨값은 각각 0.5로 증가시킬 수 있다. Cal 노드는 이 반복 도중에 Dale 노드로부터의 어떠한 라벨값 정보도 얻지 못하는데, 이는 Dale 노드가 모든 라벨값에 대하여 무효의 값을 이전에 가졌었기 때문이다. 표준화 이후에, Cal 노드의 라벨값은 Dogs:0.5, Racing:0.25, Stocks:0.25 및 Gambling:Null 이다. 다른 사용자 노드 라벨값도 거의 유사한 방식으로 수정될 수 있다.

특정한 구현예에서, 428, 430 및 432와 같은 라벨 노드는 수정되지 않는다. 그 대신에, 모든 반복에 대하여, 라벨 노드는 그들이 링크된 사용자 노드의 라벨값을 수정하기 위해 사용되는 하나 이상의 고정된 라벨값을 제공할 수 있다.

도 6c는 알고리즘의 세번째 반복 이후에 도 6a의 그래프를 나타낸다. 각각의 사용자 노드에 대한 라벨값들은 이웃하는 사용자 노드에 기초하여 계속해서 수정된다. 이 세번째 반복의 경우, Abby 노드는 아직 Gambling 라벨값을 갖지 않으며, Stocks 라벨은 Bob 및 Ernie 노드에 의하여 증가하고, Dale 노드는 Stocks 라벨에 대한 Cal 및 Ernie 노드의 이중 기여분에 기초하여 Gambling 라벨값보다 큰 Stocks 라벨값을 갖는다. 부가적으로, Cal 노드는 Racing 라벨보다 Stocks 라벨에 대하여 더 많은 기여분을 수신하며, Cal 노드는 Racing 라벨보다 Gambling 라벨에 대하여 더 많은 기여분을 수신한다.

도 6d는 알고리즘의 100회 반복 이후에 도 6a의 그래프를 나타낸다. 각각의 사용자 노드에 대한 라벨값은 정상 상태의 값에 근접하고 있다. 이 예에서, 모든 사용자 노드는 각 라벨에 대한 라벨값을 가지고 있다. Cal 노드의 경우, 라벨 Stocks와 Dogs는 가장 큰 영향력을 가지며, Racing 라벨은 Gambling 라벨보다 더 큰 값을 갖는다. 라벨 Dogs의 Ernie 노드에 대한 영향은 Abby에 대한 라벨 Gambling의 영향과 동일하다.

도 6e는 알고리즘의 1000회 반복 이후에 도 6a의 그래프를 나타낸다. 각 사용자 노드에 대한 라벨값은 사용자 노드에 대한 라벨값들이 100회 반복 이후에 얻어진 라벨값들과 거의 동일하다는 사실에 의해 알 수 있는 바와 같이 실질적으로 정상 상태 값에 도달하였다.

도 7은 사용자 관심을 추론하는데 사용하기 위한 선택적인 예제 그래프(700)이다. 일부 구현예의 경우, 그래프(700)는 도 4d와 관련하여 기술한 그래프와 거의 유사하지만, 고정된 라벨값을 주입하는 라벨 노드는 명료성을 위하여 배제되어 있다. 그래프(700)는 사용자 노드(702), 그룹 노드(704) 및 키워드 노드(706)를 포함한다. 여기서, 본 예제의 목적을 위하여 라벨은 키워드로 한다. 사용자 노드(702)는 이전에 논의한 바와 같은 멤버쉽 관계에 기초하여 그룹 노드(704)에 링크될 수 있으며, 사용자 및 그룹 노드(702, 704)는 이들 노드(702, 704)가 다른 라벨 노드에 링크되는 것과 거의 마찬가지의 방식으로 키워드 노드(706)에 링크될 수 있다.

특정한 구현예에서, 하나 이상의 키워드 노드(706)는 디스플레이를 위하여 온라인 광고를 선택하는데 사용되는 광고주가 선택한 용어에 부합하지 않는 용어를 포함하고 있다. 예컨대, 키워드 노드(708)와 연관된 키워드 "recycled tofu"는 광고주가 선택한 용어가 아닐 수 있다(비선택형 용어라고도 지칭함). 일부 구현예의 경우, 추론된 라벨 생성기(204)는 그래프의 노드에 걸쳐서 이 키워드에 관련된 라벨값을 제공하지 않는다. 대신에, 비선택형 용어가 광고주가 선택한 용어와 연관지어진다. 이러한 프로세스는 도 9c와 관련하여 더욱 자세하게 기술한다.

도 8은 광고주가 선택한 용어의 그룹을 포함하는 노드를 갖는 선택적인 예제 그래프(800)이다. 일부 구현예의 경우, 추론된 라벨 생성기는 광고주가 선택한 용어의 그룹 혹은 애드그룹 노드(710)를 포함하는 노드를 사용하여, 그래프를 통해 어떤 키워드 노드를 보급할 것인지를 결정한다. 예컨대, 애드그룹 노드는 광고주가 선택한 용어의 목록에 포함된 키워드에 링크될 수 있다.

recycled tofu 및 NASCAR 키워드 노드(708, 712) 등의 비선택형 용어를 포함하는 키워드 노드는 애드그룹 노드(710) 중 어느 것에 대해서도 에지에 의해 연결되지 않는다. 비선택형 용어를 포함하는 키워드 노드는 일부 구현예에서 그래프에 남아 있을 수 있고, 귀납적인 바이어스(Inductive Bias)의 소스를 제공할 수 있다.

도 9a 내지 9c는 그래프 내의 노드에 대한 라벨을 추론하기 위하여 사용되는 부가적인 노드를 포함하는 선택적인 예제 그래프이다. 도 9a는 광고주 노드(714)를 갖는 선택적인 예제 그래프(900)이다. 광고주 노드는 일부 구현예에서 광고주를 대표할 수 있다. 광고주 노드(714)는 광고주에 의하여 지정된 키워드를 포함하는 애드그룹 노드(710)에 그래프의 에지에 의하여 링크될 수 있다. 예컨대, 광고주(921) 노드(902)는 광고주(921)의 온라인 광고를 언제 디스플레이할 것인지를 결정하기 위해 사용되는 키워드로서 Racing 및 Stocks를 지정한 광고주와 연관되어 있을 수 있다. 이는 애드그룹 321232 노드(802)(이것은 Racing 키워드 노드와 Stocks 키워드 노드에 링크되어 있음)에 광고주(921) 노드(902)를 링크하는 에지를 갖는 그래프(900)에 의하여 도시되어 있다.

도 9b는 그래프의 노드에 대하여 라벨이 추론된 이후에 도 9a의 선택적인 예제 그래프(900)이다. 이 예에서, 그래프의 모든 노드는 이전에 논의한 알고리즘이나 방법 중 하나 이상을 이용하여 광고주가 선택한 키워드와 연관되어 있다. 도 9b에 도시한 바와 같이, Abby 노드(418)는 Dogs, Racing 및 Stocks에 대하여 라벨값 X₁, X₂ 및 X₃을 각각 갖는다. VeganVets4Life 그룹 노드, 애드그룹 123192 노드(804) 및 광고주(801) 노드는 또한 도 9b에 나타낸 바와 같이 라벨값 X₄-X₉를 포함한다.

도 9c는 광고주가 선택한 키워드에 매핑된 비선택형 키워드를 나타낸다. 이 예에서, 추론된 라벨 생성기(204)가 상술한 바와 같은 하나 이상의 알고리즘을 실행한 이후에, 상기 비선택형 키워드는 광고주에 의해 선택되지 않은 키워드에 대응하는 라벨값을 갖는다. 예컨대, NASCAR 키워드 노드(712)는 광고주(921)에 의해 선택된 키워드인 라벨 Racing에 대한 라벨값을 포함한다.

도 9a 내지 9c에 도시한 구현예에서, 모든 노드는 광고주에 의해 선택된 키워드에 직접 혹은 간접적으로 링크되어 있다. 이는 사용자가 광고주가 선택한 키워드와 직접 관련되어 있는지 여부에 관계 없이 광고주가 사용자를 타게팅할 수 있도록 한다. 예컨대, Ernie 노드(426)는 CannotDrive55 그룹 노드와의 멤버쉽 관계의 방식으로 NASCAR 노드(712)와 연관되어 있다. 광고주(921)는 키워드 Racing과 연관된 광고로 Ernie를 타게팅할 수 있는데, 이는 NASCAR 키워드 노드가 나타낸 바와 같이 Racing 키워드 노드에 매핑되어 있기 때문이다.

만약 소셜 네트워크 시스템의 신입 회원 등의 사용자가 그 사용자의 노드를 그룹의 노드에 링크함으로써 그래픽적으로 표현되는 바와 같이 라벨을 가지지 않고 그룹에 가입한다면, 광고 서버는 그 사용자에게 광고하기 위하여 해당 그룹 노드와 연계된 키워드를 사용할 수 있다. 부가적으로, 만약 사용자가 키워드와 연관되어 있다면, 추론된 라벨 생성기(204)는 회원이 가입하는 그룹과 연관된 키워드와 현재의 키워드를 결합할 수 있다.

상술한 바와 같이, 추론된 라벨 생성기는 라벨값을 결정하기 위해 다중 그래프를 사용할 수 있고, 기대되는 선험적인 분포에 기초하여 최종 라벨값을 결정하기 위해 처리된 그래프의 출력을 비교할 수 있다.

도 10은 모든 키워드가 라벨로서 사용되는 경우의 그래프(1000)이다. 그래프(1000)를 통해 모든 키워드 라벨을 보급하는 것은 그려진 소셜 네트워크 시스템에 특정된 광고주 노드(714)에 대하여 키워드 라벨을 생성하는 것이 가능하다. 추론된 라벨 생성기는 광고주가 광고 목적으로 선택해야 하는 다른 키워드에 대한 제안으로서, 특정한 광고주 노드와 연계된 키워드 라벨을 출력할 수 있다. 일부 구현예에서, 모든 키워드 대신에 키워드의 하위 세트가 그래프에 걸친 보급을 위하여 선택될 수 있다.

도 11은 광고주가 라벨로서 사용되는 경우의 그래프(1100)이다. 그래프(1100)를 통하여 광고주(혹은 광고주의 하위 세트)를 보급하는 것은 각각의 사용자 노드, 그룹 노드 혹은 키워드 노드에 대하여 광고주 라벨을 생성할 수 있다. 이는 어떤 광고주가 이들 노드 각각과 연계될 가능성이 가장 높은지를 제안할 수 있다.

도 12는 사용자가 라벨로서 사용되는 경우의 그래프(1200)이다. 그래프(1200)를 통해 사용자(혹은 사용자의 하위 세트)를 보급하는 것은 그래프에서 다른 노드 각각에 대하여 사용자 라벨을 발생시킬 수 있다. 이는 어떤 사용자가 광고 주, 그룹, 키워드 및 애드그룹과 연관될 가능성이 가장 높인지를 제안할 수 있다. 부가적으로, 만약 사용자 라벨이 사용자 노드에 대하여 생성된다면, 상기 추론된 라벨 생성기는 특정한 사용자 노드와 연관된 사용자 라벨에 기초하여 어떤 사용자가 상호 유사한지를 결정할 수 있다.

도 13은 더미(Dummy) 노드를 포함하는 그래프이다. 특정한 구현예에서, 더미 노드는 원거리의 이웃하는 노드의 영향을 줄이기 위하여 그래프(1300)에서 사용될 수 있다. 노드의 라벨이 예컨대 가장 큰 라벨값을 갖는 라벨에 기초하여 결정되는 경우에, 더미 라벨에 대하여 할당된 가중치는 무시될 수 있으며, 그 나머지 가중치가 결정 시에 사용된다. 예컨대, 더미 노드의 기여분은 (예컨대, 라벨값이 정상 상태에 도달하거나 지정된 수의 반복이 이루어진 이후에) 알고리즘의 말미에서 라벨값의 연산으로부터 제거될 수 있다.

특정한 구현예에서, 더미 노드는 추론된 라벨 생성기에 의해 생성되는 모든 그래프에서 사용 가능하다. 다른 구현예에서, 사용자는 더미 노드가 사용될 수 있는 그래프를 지정할 수 있다.

도 13은 그래프에서 모든 노드와 더미 노드가 연관되어 있는 경우의 구현예를 나타낸다. 다른 구현예에서, 더미 노드는 사용자 프로필의 내용 등에 기초한 초기의 라벨과 연계되지 않은 노드와 같이 작은 수의 노드에 할당된다.

도 14는 컴퓨터 시스템(1400)의 개략도이다. 본 시스템(1400)은 일 구현예에 따라 이전에 기술한 컴퓨터로 구현되는 방법 중 어느 것과도 연계하여 기술된 동작들을 위해 사용될 수 있다. 본 시스템(1400)은 랩탑, 데스크탑, 워크스테이션, PDA, 서버, 블레이드 서버, 메인프레임 및 기타 적절한 컴퓨터 등 다양한 형태의 디지털 컴퓨터를 포함하는 것으로 의도되어 있다. 본 시스템(1400)은 PDA, 휴대전화, 스마트폰 및 기타 유사한 연산 장치 등의 모바일 장치를 포함할 수도 있다. 부가적으로, 본 시스템은 USB(Universal Serial Bus) 플래시드라이브와 같은 휴대용 저장 매체를 포함할 수 있다. 예컨대, USB 플래시드라이브는 운영체제 및 기타 어플리케이션을 저장할 수 있다. USB 플래시드라이브는 다른 연산 장치의 USB 포트에 삽입 가능한 USB 컨넥터나 무선 송신기와 같은 입/출력 컴포넌트를 포함할 수 있다.

본 시스템(1400)은 프로세서(1410), 메모리(1420), 저장 장치(1430) 및 입/출력 장치(1440)를 포함한다. 컴포넌트(1410, 1420, 1430 및 1440) 각각은 시스템 버스(1450)를 이용하여 상호 접속된다. 상기 프로세서(1410)는 본 시스템(1400) 내에서의 실행을 위한 명령을 처리할 수 있다. 일 구현예에서, 이 프로세서(1410)는 싱글 쓰레드(Single-threaded) 프로세서이다. 다른 구현예에서, 본 프로세서(1410)는 멀티 쓰레드(Multi-threaded) 프로세서이다. 본 프로세서(1410)는 메모리(1420) 혹은 저장 장치(1430) 상에 저장된 명령을 처리하여 입/출력 장치(1440) 상의 유저 인터페이스에 대해 그래픽 정보를 디스플레이하는 것이 가능하다.

메모리(1420)는 본 시스템(1400) 내에서 정보를 저장한다. 일 구현예의 경우, 메모리(1420)는 컴퓨터로 판독 가능한 매체이다. 일 구현예에서, 메모리(1420)는 휘발성 메모리 유닛이다. 다른 구현예의 경우, 메모리(1420)는 비휘발성 메모리 유닛이다.

저장 장치(1430)는 본 시스템(1400)에 대한 대용량 저장부를 제공할 수 있다. 일 구현예의 경우, 저장 장치(1430)는 컴퓨터로 판독 가능한 매체이다. 다양한 서로 다른 구현예에서, 저장 장치(1430)는 플로피디스크 장치, 하드디스크 장치, 광학디스크 장치, 혹은 테이프 장치일 수 있다.

입/출력 장치(1440)는 본 시스템(1400)에 대한 입/출력 동작을 제공한다. 일 구현예에서, 입/출력 장치(1440)는 키보드 및/또는 포인팅 장치를 포함한다. 다른 구현예에서, 입/출력 장치(1440)는 GUI를 디스플레이하기 위한 디스플레이 유닛을 포함한다.

설명한 특징들은 디지털 전자 회로나 컴퓨터 하드웨어, 펌웨어, 소프트웨어 혹은 그들의 조합으로 구현 가능하다. 본 장치는 예컨대 프로그래머블 프로세서에 의한 실행을 위한 전파형 신호 혹은 기계로 판독 가능한 저장 장치 등의 정보 저장매체에서 실체적으로 탑재되는 컴퓨터 프로그램 제품에서 구현될 수 있으며, 방법의 스텝들은 입력 데이터에 대해 동작하고 출력을 생성함으로써 기술한 구현물의 기능들을 수행하기 위한 프로그램 명령을 실행하는 프로그래머블 프로세서에 의하여 수행될 수 있다. 상술한 특징은 데이터 저장 시스템, 하나 이상의 입력 장치 및 하나 이상의 출력 장치로 데이터와 명령을 전송하고 그것으로부터 데이터와 명령을 수신하기 위하여 결합된 적어도 하나의 프로그래머블 프로세서를 포함하는 프로그래머블 시스템 상에서 실행 가능한 하나 이상의 컴퓨터 프로그램에서 유리하게 구현될 수 있다. 컴퓨터 프로그램은 특정한 결과를 낳거나 특정한 활동을 수행하기 위하여 컴퓨터에서 직접 혹은 간접으로 사용 가능한 명령의 세트이다. 컴퓨터 프로 그램은 컴파일되거나 해석된 언어를 포함하여 어떠한 형태의 프로그램 언어로도 작성 가능하며, 독립형 프로그램이나 모듈로서 컴포넌트, 서브루틴 혹은 연산 환경에서 사용하기에 적합한 기타의 유닛을 포함하는 어떠한 형태로도 전개될 수 있다.

프로그램 명령의 실행에 적합한 프로세서는, 예컨대 범용 혹은 특수 목적의 마이크로프로세서 양자 및 어떤 종류의 디지털 컴퓨터의 단독 프로세서 내지 다중 프로세서 중 하나라도 포함한다. 일반적으로, 프로세서는 읽기 전용 메모리나 랜덤 액세스 메모리 혹은 양자로부터 명령어와 데이터를 수신할 것이다. 컴퓨터의 핵심적인 요소는 명령어와 데이터를 저장하기 위한 하나 이상의 메모리 및 명령을 수행하기 위한 프로세서이다. 또한, 컴퓨터는 일반적으로 데이터 파일을 저장하기 위한 하나 이상의 대용량 저장 장치와 통신하도록 동작 가능하게 결합되거나 그것을 포함할 것인바, 그러한 장치에는 내장 하드디스크와 이동식 디스크와 같은 자기 디스크, 자기광학 디스크 및 광학 디스크가 포함된다. 실체적으로 컴퓨터 프로그램 명령과 데이터를 탑재하기에 적합한 저장 장치는 예컨대 EPROM, EEPROM 및 플래시메모리 장치와 같은 반도체 메모리 장치, 예컨대 내부 하드디스크나 외장형 디스크와 같은 자기 디스크, 자기광학 디스크 및 CD-ROM과 DVD-ROM 디스크를 포함하여 모든 형태의 비휘발성 메모리를 포함한다. 프로세서와 메모리는 ASIC(Application-Specific Integrated Circuit)에 의해 보충되거나 그것에 통합될 수 있다.

사용자와의 상호 작용을 제공하기 위하여, 본 특징들은, 사용자에게 정보를 디스플레이하기 위하여 CRT나 LCD 모니터와 같은 디스플레이 장치를 가지고, 사용자가 컴퓨터에 입력을 제공할 수 있는 마우스나 트랙볼(Trackball)과 같은 지시 장 치 및 키보드를 갖는 컴퓨터 상에서 구현될 수 있다.

본 특징들은 데이터 서버와 같은 백엔드 컴포넌트를 포함하거나, 어플리케이션 서버나 인터넷 서버와 같은 미들웨어 컴포넌트를 포함하거나, 인터넷 브라우저나 그래픽 유저 인터페이스를 갖는 클라이언트 컴퓨터와 같은 프론트엔드 컴포넌트 혹은 그러한 백엔드, 미들웨어 혹은 프론트엔드 컴포넌트의 모든 조합을 포함하는 연산 시스템에서 구현될 수 있다. 시스템의 컴포넌트는 통신 네트워크와 같은 디지털 데이터 통신의 어떠한 형태나 매체에 의해서도 접속 가능하다. 통신 네트워크의 예로는 LAN(Local Area Network), WAN(Wide Area Network), 피어투피어 네트워크(Peer-to-peer Network, 애드혹 내지 고정된 멤버를 가짐), 그리드 연산 인프라구조 및 인터넷이 포함된다.

연산 시스템은 클라이언트와 서버를 포함할 수 있다. 클라이언트와 서버는 보통 서로 떨어져 있으며, 일반적으로는 상술한 것처럼 네트워크를 통하여 상호 작용한다. 클라이언트와 서버의 관계는 각각의 컴퓨터 상에서 구동되고 서로에 대하여 클라이언트-서버 관계를 갖는 컴퓨터 프로그램에 의하여 발생한다.

비록 약간의 구현예에 대하여 세부적으로 상술하였지만, 다른 개조가 가능하다. 특정한 구현예에서, 라벨 노드들이 고 레벨의 의미론적인(Semantic) 노드이어야 하는 것은 아니다. 그 대신에, 이들은 개개의 키워드일 수 있다. 예컨대, 이들은 모든 사용자의 자신에 관한 페이지/설명 및 모든 그룹의 설명 등에서 발생하는 키워드의 세트의 조합일 수 있다.

다른 구현예에서, 이들은 일반적이지 않은 키워드일 수 있다. 예컨대, 일반 적인 단어 "the"가 많은 정보를 제공할 수는 없지만, 비교적 일반적이지 않은 키워드 "basketball(농구)"는 그렇게 할 수 있다. 이들 유형의 단어는 예컨대 공통 TF-IDF(Term Frequency-Inverse Document Frequency) 방식을 구현하는 경우에 분류 모듈(224)에 의하여 사용 가능하다. 부가적으로, 키워드는 관심 있는 수동으로 선택한 용어를 포함하는 키워드나 온라인 광고를 타게팅하기 위해 광고주가 종종 사용하는 용어 중에서 선택될 수 있다.

특정한 구현예에서, 생성되는 단일의 그래프 혹은 복수의 그래프는 사용자가 지정하는 모든 친구들 간에 에지를 가져야 할 필요가 없다. 만약 친구가 랭크되거나 가중된다면, 상위 N명의 친구(예컨대, 사용자의 가장 친한 친구)만 선택될 수 있다. 다른 구현예에서, 추론된 라벨 생성기(204)는 각 사용자가 서로를 친구로서 지정하는 링크만 선택할 수 있다.

또 다른 구현예에서, 그래프는 가중된 에지를 가질 수 있다. 일부 구현예에서, 각각의 연결은 동일하게 가중될 수 있다. 다른 구현예에서, 에지는 다수의 인자(Factor)에 기초하여 상이하게 가중될 수 있다. 예컨대, 만약 user-A가 user-B를 user-C보다 좋아하는 것으로 지정한다면, A에서 B로의 접속은 A에서 C의 경우보다 더 강할 수 있다. 다른 예에서, 만약 user-A와 user-B 둘다 서로를 좋아하는 것으로 지정한다면, 그 접속의 강도는 더욱 강할 수 있다(예컨대, 그러한 접속은 2배 더 강할 수 있음). 또 다른 예에서, 추론된 라벨 생성기는 노드의 아웃디그리(Out-degree)에 비례하여 에지를 가중할 수 있다.

다른 가중 인자는 사용자가 한 그룹으로 다른 그룹보다 많이 식별하는지 여 부에 기초할 수 있다. 이 경우, 에지 상의 가중치는 사용자로부터의 컨텐츠 포스팅을 종종 포함하는 그룹과 같이 선호하는 그룹에 대하여 더 클 수 있다. 또한, 사용자는 다른 키워드에 대해서보다 특정 키워드에 대하여 더 강한 관계를 가질 수 있다(예컨대, 사용자는 "sports(스포츠)"라는 단어보다 "venture(모험)"이라는 단어를 훨씬 더 많이 사용할 수 있음). 사용자들 간의 가중치는 메세지, 서로의 사이트에 대한 방문 등 사용자들 간의 상호 작용의 빈도에 기초할 수도 있다.

다른 구현예에서, 에지는 '친구'가 추가된 경우에 기초하여 가중될 수 있다. 예컨대, 최근에 추가된 친구에 대한 링크는 이전에 추가된 친구보다 더 크게 가중될 수 있는데, 최근에 추가된 친구가 현재의 관심도를 나타낼 수 있기 때문이다. 다른 구현예의 경우, "더 오랜" 친구를 링크하는 에지가 더 많이 가중될 수 있다. 예컨대, 만약 친구가 잠깐 동안 친구였고 그 사용자가 주기적으로 친구를 버리는 것으로 알려져 있다면, 친구 목록에서 오래 지속된 친구가 더 높이 가중될 수 있다. 부가적으로, 사용자들 간의 유사도 메트릭스(Similarity Metrics)(예컨대, 그들이 사용하는 단어에 있어서 중첩 비율)를 사용하여 그 관계를 가중하는 것이 가능하다. 예를 들어, 용어 사용에 있어서 강한 중첩을 갖는 사용자들은 의미 있는 중첩을 갖지 않는 사용자들보다 더 크게 가중되는 링크를 가질 수 있다.

일부 구현예의 경우, 상술한 알고리즘과 방법은 수렴할 때까지 실행될 필요가 없다. 더 빨리 중지될 수 있으며, 상기 추론된 라벨 생성기는 노드에서 라벨값의 크기를 독출할 수 있다.

일부 구현예에서, 최종 결과를 결합하기 위해 사용되는 결합 가 중(Combination-Weight)이 (0, 1) 혹은 (1, 0)으로 설정될 수 있으며, 이는 그래프 중 하나만 선택하고 다른 하나는 선택하지 않는다. 부가적으로, 결합 기능은 선형적이거나 연속적이지 않을 수 있다. 예컨대, 추론된 라벨 생성기는 만약 graph-A로부터 생성된 라벨이 너무 균일하다면 예컨대 Graph-B로부터 생성된 라벨만 온라인 광고를 타게팅하는데 사용하도록 선택되는 것을 지정할 수 있다.

부가적으로, 예컨대 상술한 의사 코드와 방법(500)에서 지정된 바와 같은 '사용자'라는 용어는 실제로는 소셜 네트워크 시스템의 그룹일 수 있다. 또한, "사용자"라는 용어는 키워드, 광고주, 애드그룹 등과 같이 그래프에 기술된 다른 실체로 대체될 수 있다.

특정한 구현예에서, 사용되는 라벨의 세트는 광고를 포함할 수 있다. 예컨대, 그래프를 통하여 보급된 라벨은 하나 이상의 사용자가 클릭했던 광고를 포함할 수 있다. 이 구현예의 경우, 광고 라벨이 그래프에 걸쳐서 추론된 이후에, 각 사용자에 대하여 상기 추론된 라벨 생성기가 각 사용자가 클릭할 가능성이 있을 수 있는 광고의 세트를 출력할 수 있다.

다른 구현예의 경우, 추론된 라벨 생성기는 광고 등을 타게팅하기 위하여 사용자에 대한 라벨을 선택할 수 있으며, 여기서 라벨은 초기의 기계 학습 분류에 기초하여 얻어지거나, 추론된 라벨 생성기가 각 사용자에 대하여 라벨을 추론하기 위해 그래프 상에서 상술한 알고리즘과 방법을 실행함으로써 생성된 추론된 라벨을 사용할 수 있다.

특정한 구현예에서, 사용자들 간의 방향성 그래프에 기초하여 동일한 알고리 즘과 방법을 적용할 수 있다(예컨대, 만약 사용자 A가 사용자 B가 친구라고 말한다면, 이는 방향성이 없는 경우가 아니라 방향성이 있는 에지로서, 사용자 B가 사용자 A 역시 친구임을 지정함을 암시함).

부가적으로, 데이터 구조에서 도 4d의 그래프(440)와 같이 사용자들 간의 링크는 만약 충분한 공통의 그룹/키워드가 존재한다면 선택적일 수 있다. 예를 들어, 만약 그래프 연결성(Connectivity)의 정의된 임계값이 만족된다면(예컨대, 평균적인 사용자 노드가 적어도 2개의 다른 사용자들에 대해 2개의 에지에 의하여 접속되어 있는 경우 등), "충분한" 공통의 그룹/키워드가 존재할 수 있다.

특정한 구현예에서, 만약 label-B를 갖는 것보다 label-A를 갖는 라벨링 노드가 더 많다면, 추론된 라벨 생성기는 각각의 라벨값을 표준화하여, 각 유형에 대한 라벨값의 합계가 각 라벨에 대하여 동일하게 될 수 있다(예컨대, 모든 라벨링 노드에 걸쳐서 label-A의 합계 = 1.0 이고, 모든 라벨링 노드에 걸쳐서 label-B의 합계 = 1.0).

다른 구현예에서, 상기 알고리즘과 방법에서 기술한 바와 같은 표준화 스텝은 라벨값의 크기를 선형적으로 가중하며, 이를 1.0까지 스케일링하지만, 추론된 라벨 생성기는 다양한 표준화 혹은 표준화를 위한 비선형 기능을 사용할 수 있다.

키워드와 광고주 간의 에지는 예컨대 광고주가 작은 세트의 키워드에만 관심이 있거나 단 하나의 애드그룹을 갖는다는 점 등을 나타내기 위하여 부가될 수 있다.

부가적으로, 클릭율(Click-through-rate)이 상술한 알고리즘에 통합될 수 있 다. 일부 구현예에서, 클릭율은 광고가 열람자에게 디스플레이되거나 열람자에 의하여 선택된 횟수를 포함할 수 있다. 이 클릭율은 소셜 네트워크 상에서만 혹은 다른 웹 사이트 상에 디스플레이되는 광고에 기초하여 연산될 수 있다. 예를 들어, 클릭율은 매 시간에 기초하여 연산 가능하며, 광고는 검색 쿼리에 응답하여 검색 엔진 웹사이트 상에서 디스플레이된다. 이러한 클릭율은 소셜 네트워크에 대하여 사용되는 경우에 광고에 대한 클릭율을 평가하기 위하여 사용될 수 있다. 다른 예에서, 클릭율은 매 시간에 기초하여 연산 가능하며, 어떤 웹 사이트가 광고를 디스플레이하는지 여부에 관계 없이 웹 사이트와 연관되어 광고가 디스플레이된다(예컨대, 웹 사이트 상에 디스플레이할 광고를 제공하는 Google의 AdSense와 같은 시스템은 클릭율을 연산할 수 있음).

만약 클릭율이 별개의 시스템에 의하여 결정된다면, 추론된 라벨 생성기는 에지에 대하여 적용할 가중치를 결정할 때 이러한 정보를 요청할 수 있다. 상술한 이전의 예에서, 키워드와 애드그룹 혹은 광고주 간의 접속은 가중되지 않은 것으로 나타나 있다. 그러한 접속은 특정한 키워드와 함께 광고주/애드그룹이 갖는 클릭율을 반영하도록 역시 가중될 수 있다. 예컨대, 클릭율이 더 높을수록 가중치가 더 높다. 다른 구현예에서, 최소의 클릭율(예컨대, [기대되는 클릭율에 광고주가 입찰한 양을 곱한 것]으로부터 얻어지는 유효 기대 수익)을 갖는 접속만이 키워드와 애드그룹/광고주 간에 모델링된다. 최소 클릭율을 갖지 않는 애드그룹/광고주는 라벨을 결정하기 위해 사용되는 알고리즘이나 방법으로부터 제거될 수 있다. 또 다른 구현예의 경우, 광고의 클릭쓰루(Click-through) 피드백을 사용하여 일련의 테스트 반복에 기초하여 에지들 간의 가중치를 조정하는 것이 가능하다.

추론된 라벨 생성기는 그래프의 구조를 수정할 수 있다(예컨대, 가중된 접속 중 최하 1% 내에 속하는 접속과 같은 접속의 비율을 제거하는 것). 이는 앞서 설명한 랜덤 워크에 근사할 수 있다. 부가적으로, 모든 노드에서 모든 라벨을 관리하는 것 대신에, 추론된 라벨 생성기는 라벨의 하위 세트만을 관리할 수도 있다.

비슷한 구현예에서, 고도로 접속된 노드는 동일한 프로세서를 사용하여 처리될 수 있으며, 이는 메세지 전달(Message Passing)을 줄일 수 있다. 부가적으로, 근사화는 레이어 와이즈(Layer-wise) 방식으로 연산 가능하며, 이 경우 각각의 레이어는 예컨대 특정한 유형의 노드를 포함한다. 예를 들어, 하나의 레이어는 도 9a에 나타낸 바와 같이 사용자 노드, 다른 레이어 그룹 노드 및 다른 레이어 키워드 노드를 포함할 수 있다. 일부 구현예에서, 상술한 알고리즘과 방법은 동시에 모든 레이어가 아니라 레이어의 쌍에 대하여 연산될 수 있다. 예를 들어, 본 방법의 어떤 수의 반복은 제 1 및 제 2 레이어 간에 연산되고, 제 2 및 제 3 레이어 간에 일부, 그리고 제 3 및 제 4 레이어 간에 일부가 연산되며, 이후 본 방법을 반복할 수 있는 식이다.

부가적으로, 도면에서 묘사한 논리의 흐름은 바람직한 결과를 얻기 위해 나타낸 특정한 순서나 순차적인 순서를 요구하지 않는다. 또한, 다른 스텝이 제공될 수 있으며, 스텝이 상술한 흐름으로부터 제거될 수도 있고, 다른 컴포넌트가 상술한 시스템에 대해 부가되거나 그것으로부터 삭제될 수 있다. 예컨대, 제 1 및 제 2 데이터 저장부(206, 208)는 하드드라이브와 같은 단일의 저장 장치 내에 존재할 수 있다.

따라서, 기타의 구현예들은 다음의 청구항의 범위 내에 속하는 것이다.

Claims

컴퓨터 시스템에 의해 구현되는 방법에 있어서,

상기 컴퓨터 시스템에 의해, 소셜 네트워크의 사용자에 의하여 생성된 컨텐츠에 기초하여 컨텐츠 기반의 키워드들의 세트(a set of content-based keywords)를 생성하는 단계―여기서, 상기 소셜 네트워크를 나타내는 그래프에서 노드들이 사용자들을 대표함―;

상기 컴퓨터 시스템에 의해, 광고주 선택형 키워드들(advertiser-selected keywords)과 일치하는 상기 컨텐츠 기반 키워드들의 세트로부터의 콘텐츠 기반 키워드들을 포함하는 광고 라벨들을 갖는 사용자 노드들을 포함하는 노드들을 라벨링하는 단계―여기서, 상기 광고주 선택형 키워드들은 상기 광고주에 의해 지정된 하나 이상의 용어(term)에 기초함―; 및

각 노드에 대하여, 상기 컴퓨터 시스템에 의해, 관계에 의해 상기 각 노드에 관련된 이웃 노드(neighboring node)와 연관된 상기 광고 라벨들의 가중치에 기초하여 상기 광고 라벨들에 대한 가중치를 출력하는 단계―여기서, 상기 가중치는 상기 각 노드의 특성(characterization)에 대해 연관된 광고 레벨의 기여분(magnitude of a contribution)을 나타냄―를 포함하는 방법.
청구항 1에 있어서,

상기 관계는 소셜 관계인 방법.
청구항 2에 있어서,

상기 관계는 상기 각 노드에 의해 대표되는 사용자에 의해 지정된 친구 관계인 방법.
청구항 2에 있어서,

상기 관계는 상기 각 노드에 의해 대표되는 사용자에 의해 지정된 그룹 멤버쉽에 기초한 관계, 상기 이웃 노드들과 상기 각 노드에 의해 대표되는 상기 사용자들에 의해 생성된 컨텐츠 간의 유사성(similarity)에 기초한 관계, 및 웹 사이트 방문 패턴(web-site visiting pattern)의 유사성에 기초한 관계로 이루어진 그룹 중에서 선택되는 방법.
청구항 1에 있어서,

상기 노드들은 상기 광고주 선택형 키워드와 일치하지 않는 상기 컨텐츠 기반 키워드의 표시(representation)들을 포함하는 비선택형 키워드 노드들을 더 포함하는 방법.
청구항 5에 있어서,

상기 비선택형 키워드 노드들을 상기 광고 라벨들로 라벨링하는 단계를 더 포함하는 방법.
청구항 1에 있어서,

상기 노드들은 광고주 선택형 키워드들의 그룹의 표시들을 포함하는 애드그룹 노드(Adgroup node)들을 더 포함하는 방법.
청구항 1에 있어서,

상기 노드들은 광고주들의 표시들인 광고주 노드들을 더 포함하는 방법.
청구항 8에 있어서,

상기 광고주 선택형 키워드와 일치하지 않는 상기 컨텐츠 기반 키워드들을 포함하는 비선택형 키워드 라벨들로 상기 노드들을 라벨링하는 단계를 더 포함하는 방법.
청구항 9에 있어서,

상기 광고주를 대표하는 광고주 노드와 연관된 상기 비선택형 키워드 라벨에 기초하여 광고주가 타게팅할 수 있도록 제안된 용어(suggested term)들을 출력하는 단계를 더 포함하는 방법.
청구항 1에 있어서,

상기 사용자에 의해 생성된 상기 컨텐츠는 상기 소셜 네트워크에 의하여 호스트되는 사용자 코멘트(user comment)들이나 사용자 프로필(user profile)들을 포함하는 방법.
청구항 1에 있어서,

상기 광고 라벨은 상기 소셜 네트워크의 상기 사용자에게 디스플레이하기 위한 온라인 광고를 선택하는데 사용되는 방법.
청구항 1에 있어서,

상기 광고주 선택형 키워드는 상기 광고주에 의해 지정된 상기 용어들을 포괄(encompass)하는 카테고리들을 포함하는 방법.
청구항 1에 있어서,

상기 광고주 선택형 키워드는 상기 광고주에 의하여 지정된 상기 용어들을 포함하는 방법.
청구항 1에 있어서,

상기 소셜 네트워크의 상기 사용자들을 대표하는 상기 사용자 노드들은 각 사용자를 대표하는 각 사용자 노드 및 사용자들의 그룹들을 대표하는 그룹 노드들을 포함하는 방법.
청구항 15에 있어서,

상기 사용자 노드에 의해 대표되는 사용자가 상기 그룹 노드에 의해 대표되는 그룹에 가입하거나 상기 그룹 노드와 연관된 웹 페이지를 방문하는 경우, 그룹 노드와 연관된 상기 광고 라벨들을 사용자 노드와 연관(associate)짓는 단계를 더 포함하는 방법.
청구항 1에 있어서,

상기 노드들을 포함하고 상기 노드를 연결하는 에지(edge)들로서 상기 노드 들간의 관계들을 표현하는 그래프를 생성하는 단계를 더 포함하는 방법.
청구항 17에 있어서,

상기 에지들은 상기 관계가 양방향(bi-directional)인지 여부, 상기 노드들 간 링크의 수, 사용자가 다른 사용자의 프로필을 방문한 빈도, 및 광고주들에 의해 지정된 지불 조건(payment terms)으로 구성된 그룹 중에서 선택된 인자들에 기초하여 가중되는 방법.
청구항 17에 있어서,

상기 이웃 노드들은 에지에 의하여 상기 각 노드에 연결되는 이웃 사용자 노드(neighboring user node)들인 방법.
청구항 1에 있어서,

다른 노드들을 라벨링하는데 사용하기 위하여 노드 타입을 선택하는 단계를 더 포함하는 방법.
청구항 20에 있어서,

상기 노드들을 사용자 라벨들로 라벨링하는 단계를 더 포함하며,

상기 선택된 노드 타입은 각 사용자를 대표하는 상기 사용자 노드들을 포함하는 방법.
청구항 21에 있어서,

각 노드에 대하여, 관계에 의해 상기 각 노드에 관련된 이웃 노드들과 연관된 사용자 라벨들의 가중치에 기초하여 상기 사용자 라벨들에 대한 가중치를 출력하는 단계를 더 포함하는 방법.
청구항 21에 있어서,

어느 사용자들이 실질적으로 유사한지를, 상기 사용자 노드들과 연관된 사용자 라벨들에 기초하여 결정하는 단계를 더 포함하는 방법.
청구항 20에 있어서,

상기 노드들을 광고주 라벨들로 라벨링하는 단계를 더 포함하며,

상기 선택된 노드 타입은 광고주들을 대표하는 광고주 노드들을 포함하는 방법.
청구항 23에 있어서,

각 노드에 대하여, 관계에 의해 상기 노드에 관련된 이웃 노드들과 연관된 광고주 라벨들의 가중치에 기초하여 상기 광고주 라벨들에 대한 가중치를 출력하는 단계를 더 포함하는 방법.
청구항 23에 있어서,

상기 사용자를 대표하는 상기 사용자 노드들과 연관된 광고주 라벨들에 기초하여 어느 사용자가 어떤 광고주에 관련되어 있는지를 결정하는 단계를 더 포함하는 방법.
청구항 1에 있어서,

제 1 노드에서 시작하는 랜덤 워크 알고리즘(random walk algorithm)을 개시함으로써 상기 제 1 노드에 대한 광고 라벨에 대하여 가중치를 결정하는 단계를 더 포함하는 방법.
청구항 27에 있어서,

상기 랜덤 워크 알고리즘은 광고 라벨로서 사용되는 노드가 선택될 때까지 이전에 선택된 노드에 관련된 이웃 노드들을 순환하여(recursively) 선택하는 단계를 포함하는 방법.
청구항 28에 있어서,

상기 랜덤 워크 알고리즘은 광고 라벨들로서 사용되는 상기 노드들의 카운트(count)를 관리(maintain)하는 단계를 포함하는 방법.
청구항 29에 있어서,

상기 광고 라벨 가중치는 관리되는 상기 카운트에 기초하는 방법.
청구항 27에 있어서,

하나 이상의 부가적인 선택된 노드 각각으로부터 상기 랜덤 워크 알고리즘을 개시함으로써 상기 하나 이상의 부가적인 선택된 노드의 광고 라벨들에 대한 가중치를 결정하는 단계를 더 포함하는 방법.
청구항 1에 있어서,

각각의 이웃 노드를 선택하고 상기 광고 라벨에 대한 상기 노드의 가중치에 상기 이웃 노드의 광고 라벨들의 상기 가중치를 더함으로써, 상기 광고 라벨에 대한 상기 노드의 가중치를 결정하는 단계를 더 포함하는 방법.
청구항 32에 있어서,

상기 선택된 이웃 노드들은 광고 라벨들로서 사용되는 노드들이 아닌 방법.
청구항 33에 있어서,

미리 정해진 구간의 시간이 발생할 때까지 혹은 상기 광고 라벨에 대한 상기 노드의 가중치가 실질적인 정상 상태(steady state)에 도달할 때까지, 상기 결정을 반복하는 단계를 더 포함하는 방법.
청구항 1에 있어서,

각 노드와 연관된 상기 광고 라벨들에 대한 출력 가중치들을 표준화(normalize)하는 단계를 더 포함하는 방법.
청구항 1에 있어서,

상기 광고 라벨들의 상기 가중치에 기초하여 각각의 노드와 연관짓기 위해 하나 이상의 광고 라벨을 선택하는 단계를 더 포함하는 방법.
청구항 1에 있어서,

상기 노드들의 광고 라벨 가중치에 기초하여 상기 노드와 연관지어 디스플레이하기 위하여 온라인 광고를 전송하는 단계를 더 포함하는 방법.
청구항 1에 있어서,

상기 노드들은 라벨들을 갖는 노드들을 더 포함하며,

상기 노드들은 사용자들의 그룹을 대표하는 그룹 노드들, 광고 라벨들을 포함하는 라벨들을 대표하는 라벨 노드들, 광고주들을 대표하는 광고주 노드들, 및 광고 키워드 그룹들을 대표하는 애드그룹 노드들로 구성된 그룹 중에서 선택되는 방법.
청구항 38에 있어서,

상기 노드 중 일부에 대한 라벨 가중치들을 결정하는 단계를 더 포함하며,

상기 결정은 상기 일부의 노드 각각에 대하여, 각 이웃 노드에 대해 이웃 노드의 라벨의 라벨 가중치에 상기 노드의 라벨 가중치를 더하는 단계를 포함하는 방법.
청구항 39에 있어서,

상기 이웃 노드의 라벨의 상기 라벨 가중치가 상기 노드의 이웃에 상기 노드를 관련짓는 상기 관계에 적어도 부분적으로 기초하는 방법.
청구항 39에 있어서,

상기 이웃하는 노드는 상기 일부에 대한 상기 라벨 가중치를 결정하기 위해 사용되는 고정된 라벨 가중치(static label weight)들을 갖는 라벨 노드들을 포함하는 방법.
청구항 39에 있어서,

상기 노드들의 상기 일부의 각 노드에 대한 상기 라벨 가중치는 상기 노드에 대한 상기 라벨 가중치들의 상기 결정 이전에 시작값(starting value)으로 초기화되는 방법.
청구항 42에 있어서,

상기 시작값은 0인 방법.
컴퓨터 시스템으로 구현되는 방법에 있어서,

상기 컴퓨터 시스템에 의해, 디스플레이하기 위한 온라인 컨텐츠를 선택하는데 사용하기 위하여 광고주들에 의해 지정된 용어들에 기초하여 선택된 키워드들을 수신하는 단계;

상기 컴퓨터 시스템에 의해, 소셜 네트워크의 사용자를 대표하는 사용자 노드들 중 일부를 상기 선택된 키워드들로 라벨링하는 단계; 및

상기 컴퓨터 시스템에 의해, 각각의 사용자 노드에 대하여, 소셜 관계에 의해 상기 사용자 노드에 관련되는 이웃 사용자 노드들과 연관된 선택된 키워드들의 가중치에 기초하여 상기 선택된 키워드에 대한 가중치를 출력하는 단계를 포함하는 방법.
컴퓨터 시스템을 포함하고,

상기 컴퓨터 시스템은

프로세서;

소셜 네트워크의 사용자들의 표시들을 포함하는 라벨 노드들을 상기 사용자에 의해 생성된 컨텐츠로부터 얻어진(derive) 컨텐츠 키워드들을 포함하는 광고 라벨들로 라벨링하는 분류 모듈; 및

관계에 의하여 상기 노드에 관련되는 이웃 노드들과 연관된 광고 라벨들의 가중치에 기초하여 상기 광고 라벨들에 대한 가중치를 출력하기 위한 수단을 구비하며, 각 가중치는 상기 각 노드의 특성에 대해 연관된 광고 라벨의 기여분을 나타내는 시스템.
컴퓨터 구현 방법에 있어서,

컴퓨터 시스템에 의해, 소셜 네트워크의 제1 사용자들과 소셜 네트워크의 제2 사용자들 간의 지인 관계(acquaintance relationship)들을 식별하는 단계;

상기 컴퓨터 시스템에 의해, 상기 제1 사용자들에 의해 생성된 컨텐츠에 기초하여, 제1 키워드들을 소셜 네트워크의 제1 사용자들과 연관짓는 단계;

상기 컴퓨터 시스템에 의해, 상기 제1 키워드들에 대한 제1 가중치를 결정하는 단계;

상기 제1 키워드들. 제1 가중치들, 및 상기 지인 관계들을 사용하여 상기 컴퓨터 시스템에 의해, 하나 이상의 키워드에 대한 하나 이상의 제2 가중치에 기초하여 상기 소셜 네트워크의 제2 사용자를 위한 하나 이상의 키워드를 결정하는 단계―상기 제1 키워드들에 대한 상기 제1 가중치들은 상기 제1 사용자들과 연관된 제1 노드들로부터 상기 제2 사용자들과 연관된 제2 노드로 전송(transfer)되어 상기 하나 이상의 제2 키워드들에 대한 상기 하나 이상의 제2 가중치에 결합됨―; 및

상기 컴퓨터 시스템에 의해, 상기 결정된 하나 이상의 제2 키워드와 상기 하나 이상의 제2 가중치에 기초하여 상기 제2 사용자를 위한 광고를 출력하는 단계를 포함하는 방법.