(57)【要約】【課題】個別ユーザの履歴を処理する負荷無しで、同じ広告の重複表示を減少させる。【解決手段】ノードとなるウェブページを遷移のリンクで結合したグラフに対し、同じ色を隣接させずに塗り分けるいわゆるグラフカラーリングアルゴリズムを応用することにより、ページ遷移の前後で同じ広告が重複しないように各ウェブページに広告を割り当てることができ、個別ユーザの履歴を処理する負荷無しで、同じ広告の重複表示を減少させることが可能となる。【選択図】図１０
2011123524.tif 000002
【特許請求の範囲】
【請求項１】
ウェブページに配信する広告を割り当てる広告制御装置において、
ウェブページに割り当てようとする広告を記憶している広告記憶手段と、
ノードとなるウェブページを、ウェブページ間の遷移に対応するリンクで結合したグラフを記憶しているグラフ記憶手段と、
グラフカラーリングアルゴリズムを前記グラフに適用することにより、前記リンクの両端のウェブページに互いに異なる広告を割り当てる割当手段と、
を有することを特徴とする広告制御装置。
【請求項２】
前記割当手段は、ウェブページ間の遷移数が所定値以上であるリンクの両端のウェブページを対象として互いに異なる広告を割り当てる  ことを特徴とする請求項１記載の広告制御装置。
【請求項３】
前記割当手段は、
処理対象のグラフから未処理の任意のウェブページを選択し、
選択したウェブページのリンク数が割り当てようとする広告数より少ないかの判定を行い、少ないと判定されればそのウェブページに、リンク先のウェブページに割り当てられていない広告であって、広告間における所定の割当順序が最も早い広告を割り当てて、そのウェブページの処理を終了し、
前記判定で前記リンク数が広告数以上と判定されれば、選択したウェブページのリンク先から未処理のウェブページを一つ選択して所定のスタックに退避した後、前記判定に戻り、
未処理のウェブページが無くなれば、退避していたウェブページを前記スタックからグラフに一つ復帰してそのウェブページにはリンク先のウェブページに割り当てられていない広告であって前記割当順序が最も早い広告を割り当てる処理、を前記スタックが空になるまで繰り返す
ことを特徴とする請求項１又は２記載の広告制御装置。
【請求項４】
ウェブページに割り当てようとする広告を記憶している広告記憶手段と、ノードとなるウェブページを、ウェブページ間の遷移に対応するリンクで結合したグラフを記憶しているグラフ記憶手段と、を有するコンピュータが、ウェブページに配信する広告を割り当てる広告制御方法において、
グラフカラーリングアルゴリズムを前記グラフに適用することにより、前記リンクの両端のウェブページに互いに異なる広告を割り当てる割当ステップを
前記コンピュータが実行することを特徴とする広告制御方法。
【請求項５】
ウェブページに割り当てようとする広告を記憶している広告記憶手段と、ノードとなるウェブページを、ウェブページ間の遷移に対応するリンクで結合したグラフを記憶しているグラフ記憶手段と、を有するコンピュータを制御することにより、ウェブページに配信する広告を割り当てさせる広告制御プログラムにおいて、
グラフカラーリングアルゴリズムを前記グラフに適用することにより、前記リンクの両端のウェブページに互いに異なる広告を割り当てさせる割当ステップを
前記コンピュータに実行させることを特徴とする広告制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ウェブ広告の配信技術に関する。
【背景技術】
【０００２】
ウェブ広告の分野では、広告効果などの観点から、広告を表示する頻度を制御する工夫が各種提案されている。例えば、ユーザ個々に表示した広告の履歴を記録し参照することにより、同じユーザに対して同じ広告が重複して表示されることを防止する提案がある（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００２−３６６８３３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、上記のような従来技術では、個々のユーザごとに広告の視聴履歴を記録し、遷移先のウェブページに割り当てる新たな広告を決定しようとするたびに、前記視聴履歴を参照して判断の処理を行うものであり、サーバ側の負担が大きいという課題があった。
【０００５】
本発明は、上記のような従来技術の課題を解決するもので、その目的は、個別ユーザの履歴を処理する負荷無しで、同じ広告の重複表示を防止することである。
【課題を解決するための手段】
【０００６】
上記の目的をふまえ、本発明の一態様（１）は、ウェブページに配信する広告を割り当てる広告制御装置において、ウェブページに割り当てようとする広告を記憶している広告記憶手段と、ノードとなるウェブページを、ウェブページ間の遷移に対応するリンクで結合したグラフを記憶しているグラフ記憶手段と、グラフカラーリングアルゴリズムを前記グラフに適用することにより、前記リンクの両端のウェブページに互いに異なる広告を割り当てる割当手段と、を有することを特徴とする。
【０００７】
本発明の他の態様（４）は、上記態様を方法として捉えたもので、ウェブページに割り当てようとする広告を記憶している広告記憶手段と、ノードとなるウェブページを、ウェブページ間の遷移に対応するリンクで結合したグラフを記憶しているグラフ記憶手段と、を有するコンピュータが、ウェブページに配信する広告を割り当てる広告制御方法において、グラフカラーリングアルゴリズムを前記グラフに適用することにより、前記リンクの両端のウェブページに互いに異なる広告を割り当てる割当ステップを前記コンピュータが実行することを特徴とする。
【０００８】
本発明の他の態様（５）は、上記態様をコンピュータ・プログラムとして捉えたもので、ウェブページに割り当てようとする広告を記憶している広告記憶手段と、ノードとなるウェブページを、ウェブページ間の遷移に対応するリンクで結合したグラフを記憶しているグラフ記憶手段と、を有するコンピュータを制御することにより、ウェブページに配信する広告を割り当てさせる広告制御プログラムにおいて、グラフカラーリングアルゴリズムを前記グラフに適用することにより、前記リンクの両端のウェブページに互いに異なる広告を割り当てさせる割当ステップを前記コンピュータに実行させることを特徴とする。
【０００９】
以上のように、ノードとなるウェブページをウェブページ間の遷移に対応するリンクで結合したグラフに対し、同じ色を隣接させずに塗り分けるいわゆるグラフカラーリングアルゴリズムを応用することにより、ページ遷移の前後で同じ広告が重複しないように各ウェブページに広告を割り当てることができ、個別ユーザの履歴を処理する負荷無しで、同じ広告の重複表示を防止することが可能となる。
【００１０】
本発明の他の態様（２）は、上記いずれかの態様において、前記割当手段（ステップ）は、ウェブページ間の遷移数が所定値以上であるリンクの両端のウェブページを対象として互いに異なる広告を割り当てることを特徴とする。
【００１１】
このように、ページ遷移の前後で異なる広告を割り当てる対象を所定以上の遷移数がある遷移リンクに限定することにより、グラフの規模に応じた割り当て処理の負荷を抑制する一方、ユーザによるページ遷移の量が多いウェブページ間で確実に異なった広告を表示することが可能となる。
【００１２】
本発明の他の態様（３）は、上記いずれかの態様において、前記割当手段（ステップ）は、処理対象のグラフから未処理の任意のウェブページを選択し、選択したウェブページのリンク数が割り当てようとする広告数より少ないかの判定を行い、少ないと判定されればそのウェブページに、リンク先のウェブページに割り当てられていない広告であって、広告間における所定の割当順序が最も早い広告を割り当てて、そのウェブページの処理を終了し、前記判定で前記リンク数が広告数以上と判定されれば、選択したウェブページのリンク先から未処理のウェブページを一つ選択して所定のスタックに退避した後、前記判定に戻り、未処理のウェブページが無くなれば、退避していたウェブページを前記スタックからグラフに一つ復帰してそのウェブページにはリンク先のウェブページに割り当てられていない広告であって前記割当順序が最も早い広告を割り当てる処理、を前記スタックが空になるまで繰り返すことを特徴とする。
【００１３】
このように、単純なアルゴリズムを用いることにより割当の処理負荷が軽減できる。このため例えば、新たな広告の追加や割当順序の変更といった変動に応じて割当処理をきめ細かくやり直すことにより、広告配信の精度と効果を高水準に維持することが可能になる。
【００１４】
なお、上記の各態様に対応する方法又はプログラムといった他のカテゴリや、以下に説明するさらに具体的な各態様も、本発明に含まれる。
【発明の効果】
【００１５】
本発明によれば、個別ユーザの履歴を処理する負荷無しで、同じ広告の重複表示を減少させることができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施形態の構成を示す機能ブロック図。
【図２】本発明の実施形態における各情報（データ）を例示する図。
【図３】本発明の実施形態における処理手順を示すフローチャート。
【図４】本発明の実施形態における広告割当の一過程を示す概念図。
【図５】本発明の実施形態における広告割当の一過程を示す概念図。
【図６】本発明の実施形態における広告割当の一過程を示す概念図。
【図７】本発明の実施形態における広告割当の一過程を示す概念図。
【図８】本発明の実施形態における広告割当の一過程を示す概念図。
【図９】本発明の実施形態における広告割当の一過程を示す概念図。
【図１０】本発明の実施形態における広告割当の一過程を示す概念図。
【図１１】本発明の実施形態における広告割当の最終過程を示す概念図。
【発明を実施するための形態】
【００１７】
次に、本発明を実施するための形態（「実施形態」と呼ぶ）について、図に沿って説明する。なお、背景技術や課題などで既に述べた内容と共通の前提事項については適宜省略する。
【００１８】
〔１．構成〕
本実施形態は、図１（構成図）に示すように、ＰＣ（パーソナルコンピュータ）や携帯電話端末装置などのユーザ端末Ｔ（以下、単に「端末Ｔ」とも呼ぶ）に対し、通信ネットワークＮ（インターネット、ＬＡＮ、携帯電話網など）経由で、コンテンツ用のウェブサーバＷが、広告を組み込んだウェブページを配信する例であり、広告制御装置１（以下「本装置１」とも呼ぶ）は、各ウェブページごとに、配信する広告を予め割り当てる装置である。
【００１９】
ここで、本装置１は、一般的なコンピュータの構成として、少なくとも、ＣＰＵなどの演算制御部５と、外部記憶装置（ＨＤＤ等）や主メモリ等の記憶装置６と、通信ネットワークＮとの通信手段７（ＬＡＮアダプタなど）と、を有し、端末Ｔはこのようなコンピュータの構成に加えて入出力手段やウェブブラウザを備える（図示省略）。なお、端末Ｔと、ウェブサーバＷや本装置１との通信（図中、破線矢印で示す）は、通信ネットワークＮを通じて行う。
【００２０】
また、本装置１では、記憶装置６に予め記憶（インストール）した図示しない所定のコンピュータ・プログラムが演算制御部５を制御することで、図１に示す各手段などの要素（１０，３０など）を実現する。これら各要素のうち、情報の記憶手段は、記憶装置６において各種のデータベース（「ＤＢ」とも表す）やファイル、データ構造体、配列等の変数、システム設定値など任意の形式で実現できる。
【００２１】
これら記憶手段のうち、広告記憶手段１５は、図２（１）に例示するように、ウェブページに割り当てようとする広告をデータ（例えば、広告ＩＤごとの配信ファイル、リンク先ＵＲＬなど）として記憶している手段である。また、グラフ記憶手段２５は、ノードとなるウェブページを、ウェブページ間の遷移に対応するリンクで結合したグラフを記憶している手段であり、図２（２）の例では、ウェブページＩＤごとに、対応するＵＲＬに加え、他のどのウェブページＩＤとリンクしているかの情報項目「リンク先」を対応付けている。なお、このようなグラフの例を図４の概念図に示す。
【００２２】
なお、本実施形態では、簡潔に説明するため、ハイパーリンクによる遷移先からはブラウザのバックボタンで戻ることができる点で、リンクは双方向であるものとする。また、記憶手段以外の各手段（図１）は、以下に説明する情報処理の機能・作用を実現・実行する処理手段である。
【００２３】
〔２．作用〕
上記のように構成した本実施形態では、本装置１の割当手段３０が、各ウェブページごとに配信する広告を割り当てるが、その際、ウェブページ間の遷移数が所定値以上であるリンクの両端のウェブページを対象として、グラフカラーリングアルゴリズムを前記グラフに適用することにより、前記リンクの両端のウェブページに互いに異なる広告を割り当てる。その処理手順を図３のフローチャートに示す。
【００２４】
なお、その前提として、本装置１の遷移数取得手段１０は、ウェブサーバＷが不特定多数の端末Ｔから受け付けるページリクエストの履歴についてウェブサーバＷから転送を受けるなどにより、所定期間（例えば最新２４時間、１週間など）内における各ウェブページ間の遷移数を取得し、グラフ記憶手段２５を随時更新する。例えば、図２（２）の例では、ウェブページＶ１−Ｖ２間のリンクにおける遷移数は５千８百万である。
【００２５】
〔２−１．フローの内容〕
図３の処理手順では、ウェブページに広告を割り当てようとする際、まず、割当手段３０は、グラフ記憶手段２５に記憶されているグラフから、ウェブページ間の遷移数が所定の閾（しきい）値以上であるリンクを持つウェブページを、広告割り当て対象として抽出する（ステップＳ１１）。なお、以下、「Ｇ」はステップＳ１１において広告割り当て対象として抽出したウェブページを含むグラフ、「Ａ」は割り当てようとする広告数、「Ｖ」はグラフＧに含まれる個々のウェブページ、「degree(Ｖ)」は各ウェブページＶからグラフＧ内の他のウェブページに張られたリンク数、とする（ステップＳ１２）。
【００２６】
また、ここでは、図４に例示するように、Ｖ１〜Ｖ６を含むグラフＧを広告割り当て対象として抽出し、割り当てようとする広告数は「甲」「乙」「丙」「丁」の４種とし、これら広告間の割当順序は最優先の「甲」から始まって、→「乙」→「丙」→「丁」とする。
【００２７】
続いて、割当手段３０は、処理対象のグラフＧから未処理の任意のウェブページＶを選択し（ステップＳ１３）、選択したウェブページＶのリンク数degree(Ｖ)が、割り当てようとする広告数Ａより少ないかの判定を行い（ステップＳ１４）、少ないと判定されれば（ステップＳ１４：「ＹＥＳ」）、その選択したウェブページＶに、グラフＧ内でのリンク先のウェブページに割り当てられていない広告であって、広告間における所定の割当順序が最も早い広告を割り当てて（ステップＳ１６）、その選択したウェブページＶの処理を終了する。
【００２８】
一方、割当手段３０は、前記判定（ステップＳ１４）において、選択したウェブページＶの前記リンク数degree(Ｖ)が広告数以上と判定すれば（ステップＳ１４：「ＮＯ」）、選択したウェブページＶのグラフＧ内でのリンク先から未処理のウェブページを一つ選択し所定のスタックに退避した後、前記判定に戻る（ステップＳ１５）。
【００２９】
ウェブページＶの処理を終了した時点で未処理のウェブページがあれば（ステップＳ１７：「ＹＥＳ」）、次のウェブページＶの選択（ステップＳ１３）からの処理に戻るが、未処理のウェブページが無ければ（ステップＳ１７：「ＮＯ」）、スタックが空か判断し、空なら処理を終了する（ステップＳ１８：「ＹＥＳ」）。一方、この判断で空でなければ（ステップＳ１８：「ＮＯ」）、退避していたウェブページを前記スタックからグラフＧに一つ復帰し、そのウェブページにはグラフＧ内でのリンク先のウェブページに割り当てられていない広告であって前記割当順序が最も早い広告を割り当て（ステップＳ１９）、スタックが空かの判断（ステップＳ１８）に戻る。
【００３０】
〔２−２．具体例〕
上記のフローにしたがった割当手段３０による処理の具体例として、例えば、図４のグラフから未処理のウェブページＶ１を選択した場合（ステップＳ１３）、そのリンク数degree(Ｖ１)はＶ２，Ｖ３，Ｖ４との間の３つで、広告数Ａ＝４より少ない（ステップＳ１４：「ＹＥＳ」）。また、この時点では未だどの広告も、どのウェブページにも割り当てられていないため、このウェブページＶ１には割り当て順序が最も早い「甲」を割り当てる（ステップＳ１６、図５）。
【００３１】
この図５の時点では、まだ未処理のウェブページＶ２〜Ｖ６があり、次にウェブページＶ２については、ウェブページＶ１と同様の処理（ステップＳ１３〜Ｓ１７）により広告「乙」を割り当てる（図６）。一方、その後ウェブページＶ３を選択した際は、リンク数degree(Ｖ３)はＶ１，Ｖ２，Ｖ４，Ｖ５，Ｖ６との間の５つで、広告数Ａ＝４以上と判定し（ステップＳ１４：「ＮＯ」）、選択したウェブページＶ３のリンク先から未処理のウェブページＶ４を選択してスタックＫに退避した後（ステップＳ１５、図７）、前記判定に戻る（ステップＳ１４）。
【００３２】
この状態で（図７）再度判定しても、ウェブページＶ３のリンク数degree(Ｖ３)はＶ１，Ｖ２，Ｖ５，Ｖ６との間の４つで、広告数Ａ＝４以上であるから（ステップＳ１４：「ＮＯ」）、ウェブページＶ３の残るリンク先からさらに未処理のウェブページＶ５を選択してスタックＫに退避した後（ステップＳ１５、図８）、さらに判定に戻る（ステップＳ１４）。
【００３３】
この時点では（図８）、ウェブページＶ３のリンク数degree(Ｖ３)はＶ１，Ｖ２，Ｖ６との間の３つで、広告数Ａ＝４より少ないと判定するので（ステップＳ１４：「ＹＥＳ」）、現在選択しているウェブページＶ３には、リンク先のウェブページＶ１、Ｖ２、Ｖ６のいずれも割り当てられていない広告で割り当て順序が最も早い「丙」を割り当てる（ステップＳ１６、図９）。
【００３４】
次に残っている未処理のウェブページＶ６を選択し、ウェブページＶ１，Ｖ２と同様の処理（ステップＳ１３〜Ｓ１７）により広告「甲」を割り当て（図１０）、未処理のウェブページが尽きた後（ステップＳ１７：「ＮＯ」）、スタックＫからウェブページＶ５，Ｖ４を順次、グラフＧに復帰しつつそれぞれ「丁」「乙」を割り当て（ステップＳ１９、図１１）、処理を終了する。
【００３５】
なお、割当手段３０は、以上のような割当の結果を所定の割当記憶手段３５に記憶させ（例えば図２（３））、このように割り当てた広告については、対応するウェブページを端末ＴがウェブサーバＷに要求すると、どのウェブページを要求されたかをウェブサーバＷが本装置１に伝達し、それを受けて広告提供手段４０が対応する広告をウェブサーバＷへ渡し、ウェブサーバＷはその広告を組み込んだウェブページを端末に配信する。
【００３６】
〔３．効果〕
以上のように、本実施形態では、ノードとなるウェブページを遷移のリンクで結合したグラフに対し、同じ色を隣接させずに塗り分けるいわゆるグラフカラーリングアルゴリズムを応用することにより、ページ遷移の前後で同じ広告が重複しないように各ウェブページに広告を割り当てることができる。例えば、図１１の割り当て結果では、どのウェブページからどのウェブページに遷移しても、遷移の前後で同じ広告が表示されることはない。すなわち、本実施形態では、個別ユーザの履歴を処理する負荷無しで、同じ広告の重複表示を減少させることが可能となる。
【００３７】
特に、本実施形態では、ページ遷移の前後で異なる広告を割り当てる対象を所定以上の遷移数がある遷移リンクに限定することにより（ステップＳ１１）、グラフの規模に応じた割り当て処理の負荷を抑制する一方、ユーザによるページ遷移の量が多いウェブページ間で確実に異なった広告を表示することが可能となる。
【００３８】
また、本実施形態では、スタックを活用した単純なアルゴリズムを用いることにより（図３〜図１１）割当の処理負荷が軽減できる。このため例えば、新たな広告の追加や割当順序の変更といった変動に応じて割当処理をきめ細かくやり直すことにより、広告配信の精度と効果を高水準に維持することが可能になる。
【００３９】
〔４．他の実施形態〕
なお、上記各実施形態は例示に過ぎず、本発明は、以下に例示するものやそれ以外の他の実施態様も含むものである。例えば、上記実施形態で示した各手段などの要素は、コンピュータの演算制御部に限らず、ワイヤードロジック等に基づく電子回路など他の情報処理機構で実現してもよい。また、各構成図、データの図、フローチャートの図などは例示に過ぎず、各要素の有無、その順序や具体的内容などは適宜変更可能である。
【００４０】
例えば、「広告」は静止画、動画など種類は問わず、また、割り当てる広告の数も上記実施形態で示した４種に限らず任意である。また、「リンク」の種類や趣旨も任意で、例えば片方向のリンクでもよい。また、本発明で用いるグラフカラーリングアルゴリズムは上記実施形態に示したものには限定されないので、スタックの使用も必須ではない。
【００４１】
また、本発明の装置（本装置１）は、複数のサーバコンピュータで実現してもよく、また、機能によっては外部のプラットフォーム等をＡＰＩ（アプリケーション・プログラム・インタフェース）やネットワークコンピューティングなどで呼び出して実現するなど、構成は柔軟に変更できる。また、本発明の広告制御装置は、広告を提供若しくは配信する手段を含んでも含まなくてもよいし、広告の配信サーバや、コンテンツ用のウェブサーバなどと一体化してもよい。また、本発明は、端末Ｔを含むシステム全体や、システム全体に対応する情報処理の方法やコンピュータ・プログラムなどとしても把握することもできる。
【符号の説明】
【００４２】
１  広告制御装置（本装置）
５  演算制御部
６  記憶装置
７  通信手段
１０  遷移数取得手段
１５  広告記憶手段
２５  グラフ記憶手段
３０  割当手段
Ｎ  通信ネットワーク
Ｗ  ウェブサーバ
Ｔ  ユーザ端末
Ｖ（Ｖ１〜Ｖ６）  ウェブページ
Ｋ  スタック
【図１】
2011123524.tif 000003
【図２】
2011123524.tif 000004
【図３】
2011123524.tif 000005
【図４】
2011123524.tif 000006
【図５】
2011123524.tif 000007
【図６】
2011123524.tif 000008
【図７】
2011123524.tif 000009
【図８】
2011123524.tif 000010
【図９】
2011123524.tif 000011
【図１０】
2011123524.tif 000012
【図１１】
2011123524.tif 000013