আজ আমরা গ্রাফ লাপ্লাসিয়ান দিয়ে ডিফিউশন ইকুয়েশনের চৌদ্দগুষ্ঠি উদ্ধার করব। নো আষাঢ়ে প্যাঁচাল। সরাসরি কাজে নামছি।

গত পোস্টে দেখেছি, ডিফিউশন ইকুয়েশনে ম্যাট্রিক্স $L$ লাপ্লাসিয়ানের রূপ ধরে বসে আছে। এবং,

\begin{eqnarray}
L = D-A
\end{eqnarray}

এখানে $D$ ম্যাট্রিক্সটার ডায়াগনাল বরাবর বিভিন্ন ভার্টেক্সের ডিগ্রীঃ $k_1,k_2,\ldots, k_n$, এবং বাদবাকি এন্ট্রি গুলো জিরো। আর $A$ হল আমাদের অতি প্রিয় এ্যাডজেসেন্সি ম্যাট্রিক্স। আপাতত আনডিরেক্টেড গ্রাফের ক্ষেত্রেই সীমাবদ্ধ থাকছি। তাই $A$ আপাতত সিমেট্রিক। তাহলে $L$ ম্যাট্রিক্সটিও সিমেট্রিক। সুতরাং

\begin{eqnarray}
L =
\begin{cases}
k_i & if \ \ i=j \\
-A_{ij} & if \ \ i\neq j \\
\end{cases}
\end{eqnarray}

একটা সিমেট্রিক ম্যাট্রিক্সের চমৎকারিত্বটা কোথায় বলুনতো? লিনিয়ার এ্যালজেব্রা বলে, একটা সিমেট্রিক ম্যাট্রিক্সের আইগেনভ্যালু গুলো রিয়াল, এবং করেস্পন্ডিং আইগেনভেক্টর গুলো একটার সাথে আরেকটা অর্থগনাল। এই স্টেটমেন্টটা একটা কোটিটাকার স্টেটমেন্ট। মাথায় পার্মানেন্ট মেমরীতে স্টোর করে ফেলুন।

আমাদের গ্রাফ-লাপ্লাসিয়ান $L$ যেহেতু সিমেট্রিক ম্যাট্রিক্স, তাই নিঃসন্দেহে, তার আইগেনভেক্টর গুলি অর্থগনাল। ভেক্টরগুলিকে একটু ধৈর্য্য ধরে নর্মালাইজ করে ফেললে সেগুলো অর্থনর্মাল সেট অফ ভেক্টরস ${v_i}$-এ পরিণত হবে। অর্থাৎ

\begin{eqnarray}
\langle v_i, v_j \rangle = v_i^T v_j = \delta_{ij}
\end{eqnarray}

$\delta_{ij}$ অবশ্যই ক্রনেকার’স ডেল্টা। এবং ধরে নিচ্ছি, আইগেনভেক্টর $v_i$ এর করেসপন্ডিং আইগেনভ্যালু $\lambda_i$. তাহলে,

\begin{eqnarray}
L v_i = \lambda_i v_i
\end{eqnarray}

এবার ডিফিউশন ইকুয়েশনে ফেরা যাক।
\begin{eqnarray}
\frac{d\Psi}{dt} + C L \Psi = 0 \nonumber
\end{eqnarray}

খেয়াল করুন, আইগেনভেক্টরের সেট, ${v_i}$ একটি কমপ্লিট সেট অফ অর্থনর্মাল ভেক্টরস। তাই তারা আসলে $n$-ডাইমেনশনাল ইউক্লিডিয়ান স্পেসের একটা বেসিস। অর্থাৎ $v_1, v_2, \ldots, v_n$ ভেক্টরগুলির লিনিয়ার কম্বিনেশনে যেকোন $n$-ডিমেনশনাল ইউক্লিডিয়ান ভেক্টরকে প্রকাশ করা যাবে। আগের পোস্টে আমরা দেখেছি,
$\Psi = \left(\psi_1(t), \psi_2(t), \ldots ,\psi_n(t)\right)$ একটা $n$-ডাইমেনশনাল ইউক্লিডিয়ান ভেক্টর। তাই নিঃসংকোচে লেখা যায়,

\begin{eqnarray}
\Psi = \sum_{i=1}^n a_i v_i
\label{eq:LinComb}
\end{eqnarray}

কোফিশিয়েন্ট গুলো অবশ্যই সময়ের ফাংশনঃ $a_i = a_i(t)$। কারন $v_i$-দের কোন টাইম ডিপেন্ডেন্স নেই। এবার ডিফিউশন ইকুয়েশনে $\Psi$-এর জায়গায় \eqref{eq:LinComb} থেকে পাওয়া ভ্যালুটি বসিয়ে দিলে দ্যাখা যাক কী হয়ঃ

\begin{eqnarray}
\frac{d\Psi}{dt} + C L \Psi = 0 \nonumber \\
\frac{d}{dt}(\sum_{i} a_i v_i) + C L \sum_{i} a_i v_i = 0 \nonumber \\
\sum_{i} \frac{d}{dt} (a_i v_i) + C \sum_{i} a_i Lv_i = 0 \nonumber \\
\sum_{i}\left[ \frac{d}{dt} (a_i) \ v_i + a_i \frac{d}{dt} (v_i) \right]
+
C \sum_{i} a_i \lambda_i v_i = 0
\nonumber
\\
\sum_{i} \left[ \frac{da_i}{dt}
+
C a_i \lambda_i \right] v_i = 0
\label{eq:LinIndependence}
\end{eqnarray}

${v_i}$ একটি বেসিস সেট। সুতরাং, তার ভেক্টর গুলো লিনিয়ারলি ইন্ডিপেন্ডেন্ট। তাই লিনিয়ার ইন্ডিপেন্ডেন্সের সংজ্ঞা অনুসারে ইকুয়েশন \eqref{eq:LinIndependence}-এ স্কয়্যার-ব্র্যাকেটের ভেতরের জিনিসটা $i$-এর সব ভ্যালু’র জন্য শূন্য। তাই,

\begin{eqnarray}
\frac{da_i}{dt} + C a_i \lambda_i = 0
\nonumber \\
\int \frac{da_i}{a_i} = -C \int \lambda_i dt
\nonumber \\
\ln(a_i) = -C\lambda_i t + \ln\gamma
\nonumber \\
\ln \left( \frac{a_i}{\gamma} \right) = -C\lambda_i t
\nonumber \\
\therefore \quad a_i(t) = \gamma e^{-C\lambda_i t}
\label{eq:aSolution}
\end{eqnarray}

ইন্টিগ্রাল কনস্ট্যান্ট $\gamma$’র মান বের করাটা খুবই সহজ। কারন,
\begin{eqnarray}
\quad a_i(0) = \gamma e^{-C\lambda_i 0} = \gamma
\nonumber \\
\therefore \quad \gamma = a_i(0)
\end{eqnarray}

সুতরাং, ইকুয়েশন \eqref{eq:aSolution} থেকেঃ

\begin{eqnarray}
a_i(t) = a_i(0) e^{-C\lambda_i t}
\end{eqnarray}

এবং ফাইনালি
\begin{eqnarray}
\Psi = \sum_i a_i(t)\ v_i
\nonumber \\
\Psi = \sum_i a_i(0) e^{-C\lambda_i t} \ v_i
\label{eq:compactSol}
\end{eqnarray}

আহ! ডিফিউশন ইকুয়েশন সলভ হয়ে গেল! কী অপূর্ব!

একটা জিনিস খেয়াল করুন, \eqref{eq:compactSol} কিন্তু একটা ম্যাট্রিক্স ইকুয়েশন। কারন বামদিকে $\Psi$ একটা ভেক্টর, এবং ডানদিকে $v_i$ একটা ভেক্টর। আমি বরং ভেঙ্গেই লিখি জিনিসটা।

কম্পনেন্ট-ওয়াইজ যদি ভেক্টর $v_i = (v_i^1, v_i^2, \ldots , v_i^n)$ হয়, তাহলেঃ

\begin{eqnarray}
\left(
\begin{matrix}
\psi_1(t) \\ \psi_2(t) \\ \vdots \\ \psi_n(t)
\end{matrix}
\right)
\ =\
a_1(0)e^{-C\lambda_1 t}
\left(
\begin{matrix}
v_1^1 \\ v_1^2 \\ \vdots \\ v_1^n
\end{matrix}
\right)
\ + \
a_2(0)e^{-C\lambda_2 t}
\left(
\begin{matrix}
v_2^1 \\ v_2^2 \\ \vdots \\ v_2^n
\end{matrix}
\right)
+
\ldots
+
a_n(0)e^{-C\lambda_n t}
\left(
\begin{matrix}
v_n^1 \\ v_n^2 \\ \vdots \\ v_n^n
\end{matrix}
\right)
\label{eq:elaboSolution}
\end{eqnarray}

ইকুয়েশন \eqref{eq:compactSol} এবং \eqref{eq:elaboSolution} -এর মধ্যে বিন্দুমাত্র পার্থক্য নেই। শুধু সব কিছুকে ভেঙ্গে-চুরে করে লিখেছি।

1D ল্যাটিস
থিওরি তো হল। এবার ছবিতে জিনিসটা কেমন দ্যাখা যাবে সেটা একটু চেষ্টা করা যাক। কমপ্লিকেটেড নেটওয়ার্ককে ভিজুয়ালাইজ করার জন্য প্রোগ্রাম লেখা সময়স্বাপেক্ষ ব্যাপার (এবং, আমি আপাতত পারিওনা সেটা :p )। আমরা এই মুহুর্তে একটা 1D ল্যাটিস দিয়ে ডিফিউশনের একটা খেলনা মডেল বানানোর চেষ্টা করব।

আপাতত ৫টা ভার্টেক্সই থাকুক। এই ৫টা ভার্টেক্সের ভেতরেই আগের পোস্টের সেই ডিটার্জেন্টের সুবাস ছড়িয়ে পড়বে। ধরা যাক $t=0$ সময়ে ভার্টেক্স-৩ ‘এ সুবাসের পরিমান সর্বোচ্চ। ভার্টেক্স-২ এবং ৪-এ তারচে একটু কম, ১ এবং ৫-এ তারচেয়েও কম। তাহলে $t= 0$-সময়ে ভার্টেক্স-৩ ‘এ $\psi$-এর ভ্যালু, তথা সুবাসের মান হাই। ঠিক নিচের ছবিটির মত।

আমাদের কমনসেন্স অনুযায়ী অন্তত এতটুকু নিশ্চিত যে, ভার্টেক্স-৩ ‘এ সুবাস ধীরে ধীরে কমবে, এবং ভার্টেক্স ১ এবং ৫-এ সুবাস ধীরে ধীরে বাড়বে। অর্থাৎ সময় বাড়ার সাথে সাথে $\psi_3$ কমবে এবং $\psi_1$ ও $\psi_5$ বাড়বে। (তা-ই তো হবার কথা। ছোটবেলায় পড়া ব্যাপনের সংজ্ঞা মনে আছে? উচ্চঘনত্বের স্থান হইতে কোন বস্তুর স্বতঃস্ফুর্তভাবে নিম্নঘনত্বের স্থানের দিকে ধাবিত হইবার ঘটনাকেই.. ইত্যাদি।)

$\psi_i(t)$-এর ভ্যালু গুলো আমরা পাব ইকুয়েশন \eqref{eq:elaboSolution} থেকে। কিন্তু ওখানকার ইনিশিয়াল কন্ডিশন $a_1(0), a_2(0), \ldots, a_n(0)$ গুলোকে কী করে পাব? আসলে, একটা এক্সপেরিমেন্টের ইনিশিয়াল কন্ডিশন নির্ধারণ করে এক্সপেরিমেন্টালিস্ট। প্রসেস নিজে থেকে তো আর ওগুলো ঠিক করবেনা, আমরা ঠিক করে দিলে সেই অনুযায়ী প্রসেস আগাবে। এই খেলনা মডেলের জন্য আমাদেরকেই ভেবে-টেবে সবগুলো $a_i(0)$ বসিয়ে দিতে হবে। ডিফিউশন কনস্ট্যান্ট $C$-এর মান যেহেতু – কী ধরণের নেটওয়ার্ক -তার উপর নির্ভর করে, তাই $C$’কেও আমরাই ধরে নেব একটা কিছু। বাকি থাকে গ্রাফ-লাপ্লাসিয়ানের আইগেনভ্যালু এবং আইগেনভেক্টর গুলো। সেগুলো কিভাবে কম্পিউট করব?

আমাদের নেটওয়ার্কটির গ্রাফ-লাপ্লাসিয়ান আমরা জানি। কারন আমরা প্রতিটি ভার্টেক্সের ডিগ্রী এবং পুরো নেটওয়ার্কের এ্যাডজেসেন্সি ম্যাট্রিক্স জানি। মুহুর্তেই $L = D-A$ বেরিয়ে পড়বে। বাড়িরকাজ দিয়ে দিলাম 😉 . এরপর আমি যেটা করেছি, সেটা হল, FreeMat দিয়ে $L$-এর আইগেনভ্যালু এবং করেসপন্ডিং আইগেনভেক্টর গুলো বের করেছি। আমার কম্পিউটারে ম্যাথম্যাটিকা নেই। এখানে ডাউনলোড-ফাউনলোড করতে সাহসও হয়না। কানধরে সোজা হাজতের ভাত খাইয়ে দেওয়ার সম্ভবনা অতীব প্রবল। যাহোক, আইগেনভ্যালু এবং আইগেনভেক্টর গুলোকে $t$-এর বিভিন্ন মানের জন্য ইকুয়েশন \eqref{eq:elaboSolution}-এ বসিয়ে দিলেই বিভিন্ন $\psi_i(t)$ বেরিয়ে পড়বে।

$t=0$ থেকে $t=15$ পর্যন্ত ফ্রীম্যাট যে প্লট দিলো, তার ওপর কিছু রঙচং ঢেলে সিকুয়েনশিয়ালি জোড়া লাগিয়ে নিচের এ্যানিমেশনটা পেয়ে গেলাম।

বেশ বোঝা যাচ্ছে, যে সব $\psi_i(t)$ গুলোই সময় বাড়ার সাথে সাথে একই ভ্যালুতে পৌছে যাওয়ার চেষ্টা করছে। অর্থাৎ, ডিটারজেন্টের সুবাস ঘরের ভেতর সবখানে সমান ভাবে ছড়িয়ে যাওয়ার চেষ্টা করছে। ভারিক্কি কথায়, সিস্টেমটি ইকুইলিব্রিয়ামে পৌঁছানোর চেষ্টা করছে।

$t=15$ -এর পর তেমন উল্লেখযোগ্য কোন পরিবর্তন আমার চোখে পড়লনা। এমনকি $t=1500$-ও দেখতে $t=15$-এর মতই প্রায়।

এবার আপনাদের পালা। 2D, 3D তে ডিফিউশনের মডেল বানিয়ে সিমুলেশন করে ফাটিয়ে ফেলুন। আমি ততক্ষণ পরের পোস্টে কী লেখা যায় ভাবি।

সে পর্যন্ত শুভকামনা!
: -)

.

নেটওয়ার্ক উপাখ্যান সিরিজের পোস্ট গুলোঃ   ১   ২   ৩   ৪   ৫   ৬

Author: Galib Hassan

Mischief Managed.. 😉