দ্বিভাগীয় গ্রাফ (Bipartite Graphs) এবং তার প্রয়োগ
একটি দ্বিভাগীয় গ্রাফে ভার্টেক্সগুলো দুটি আলাদা সেটে ভাগ করা যায় যেন প্রতিটি এজ এক সেটের একটি ভার্টেক্সকে অন্য সেটের একটি ভার্টেক্সের সাথে সংযুক্ত করে। AllElectronics ব্যবহারকারীর ক্রয় ডেটার জন্য, এক সেটের ভার্টেক্সগুলো ব্যবহারকারীকে নির্দেশ করে (প্রতি ব্যবহারকারী প্রতি ভার্টেক্স), অন্য সেট পণ্যকে নির্দেশ করে (প্রতি পণ্য প্রতি ভার্টেক্স)। একটি এজ একজন ব্যবহারকারীকে একটি পণ্যের সাথে সংযুক্ত করে, যা সেই পণ্যের ক্রয়কে বোঝায়।
প্রয়োগের ক্ষেত্রসমূহ
১. ওয়েব সার্চ ইঞ্জিন
ওয়েব সার্চ ইঞ্জিনে সার্চ লগ আর্কাইভ করা হয় ব্যবহারকারীর কোয়েরি এবং সংশ্লিষ্ট ক্লিক-থ্রু ডেটা সংরক্ষণ করতে। (ক্লিক-থ্রু ডেটা বলে আমরা বুঝি সার্চ ফলাফল হিসেবে প্রদত্ত পেজগুলোর মধ্যে ব্যবহারকারী কোন পেজে ক্লিক করেছে।)
কোয়েরি ও ক্লিক-থ্রু ডেটাকে একটি দ্বিভাগীয় গ্রাফ দিয়ে উপস্থাপন করা যায়, যেখানে দুটি ভার্টেক্স সেট যথাক্রমে কোয়েরি ও ওয়েব পেজ। একটি এজ একটি কোয়েরিকে একটি ওয়েব পেজের সাথে সংযুক্ত করে যদি ব্যবহারকারী সেই কোয়েরি করার সময় ওই ওয়েব পেজে ক্লিক করে। কোয়েরি-ওয়েব পেজ দ্বিভাগীয় গ্রাফের ওপর ক্লাস্টার বিশ্লেষণ দিয়ে মূল্যবান তথ্য প্রাপ্য।
উদাহরণস্বরূপ, যদি একাধিক কোয়েরির ক্লিক-থ্রু ডেটা একই হয়, তবে সেগুলি ভিন্ন ভাষায় হলেও একই অর্থ বোঝাতে পারে তা চিহ্নিত করা যায়। কিছু ওয়েব পেজ ওয়েবে একটি নির্দেশিত গ্রাফ (ডাইরেক্টেড গ্রাফ) বা ওয়েব গ্রাফ গঠন করে, যেখানে প্রতিটি ওয়েব পেজ একটি ভার্টেক্স এবং প্রতিটি হাইপারলিংক একটি এজ যা সোর্স পেজ থেকে ডেস্টিনেশন পেজের দিকে নির্দেশ করে। ওয়েব গ্রাফের ওপর ক্লাস্টার বিশ্লেষণ কমিউনিটি চিহ্নিত করতে, হাব ও প্রামাণিক ওয়েব পেজ আবিষ্কার করতে এবং ওয়েব স্প্যাম শনাক্ত করতে সাহায্য করে।
২. সোশ্যাল নেটওয়ার্ক
একটি সোশ্যাল নেটওয়ার্ক হলো একটি সোশ্যাল কাঠামো। এটি একটি গ্রাফ হিসেবে উপস্থাপন করা যায়, যেখানে ভার্টেক্সগুলো হলো ব্যক্তি বা সংগঠন, এবং সংযোগগুলো হলো ভার্টেক্সগুলোর মধ্যে পারস্পরিক নির্ভরশীলতা, যা বন্ধুত্ব, সাধারণ আগ্রহ বা সহযোগিতামূলক কার্যকলাপ বোঝায়। AllElectronics ব্যবহারকারীরা একটি সোশ্যাল নেটওয়ার্ক গঠন করে, যেখানে প্রতিটি ব্যবহারকারী একটি ভার্টেক্স, এবং দুজন ব্যবহারকারীর মধ্যে একটি এজ থাকে যদি তারা একে অপরকে চিনে।
ব্যবহারকারী সম্পর্কের ম্যানেজার হিসেবে, ক্লাস্টার বিশ্লেষণ দিয়ে AllElectronics-এর সোশ্যাল ওয়েব থেকে উপকারী তথ্য প্রাপ্ত করা আকর্ষণীয়। নেটওয়ার্ক থেকে ক্লাস্টার প্রাপ্ত করা যায়, যেখানে ব্যবহারকারীরা একে অপরকে চিনে বা সাধারণ বন্ধু থাকে। একটি ক্লাস্টারের মধ্যে থাকা ব্যবহারকারীরা ক্রয় সিদ্ধান্ত গ্রহণে একে অপরকে প্রভাবিত করতে পারে। আরও, যোগাযোগ মাধ্যম তৈরি করা যায় যাতে ক্লাস্টারের "শিরোমণি"দের কাছে প্রোমোশনাল তথ্য দ্রুত ছড়িয়ে দেওয়া যায়।
নেটওয়ার্কটি একটি ওজনযুক্ত গ্রাফ (weighted graph) কারণ দুজন লেখকের মধ্যে একটি এজ একটি ওজন তৈরি করতে পারে যা সহযোগিতার বলavaisry বোঝায় (যেমন দুজন লেখক কতগুলো পাবলিকেশন সহ-লেখা করেছেন)।
