Laplacian matrix
গ্রাফ তত্ত্বের গাণিতিক ক্ষেত্রে, ল্যাপলেসিয়ান ম্যাট্রিক্স, যাকে গ্রাফ ল্যাপলেসিয়ান, অ্যাডমিট্যান্স ম্যাট্রিক্স, কির্চফ ম্যাট্রিক্স বা বিচ্ছিন্ন ল্যাপলেসিয়ানও বলা হয়, একটি গ্রাফের একটি ম্যাট্রিক্স উপস্থাপনা। পিয়েরে-সাইমন ল্যাপলেসের নামে নামকরণ করা, গ্রাফ ল্যাপলেসিয়ান ম্যাট্রিক্সকে একটি গ্রাফের নেতিবাচক বিচ্ছিন্ন ল্যাপলেস অপারেটরের একটি ম্যাট্রিক্স রূপ হিসাবে দেখা যেতে পারে যা সীমাবদ্ধ পার্থক্য পদ্ধতি দ্বারা প্রাপ্ত নেতিবাচক অবিচ্ছিন্ন ল্যাপলেসিয়ানকে আনুমানিক করে। ল্যাপলেসিয়ান ম্যাট্রিক্স একটি গ্রাফের অনেক দরকারী বৈশিষ্ট্যের সাথে সম্পর্কিত। কির্চফের উপপাদ্যের সাথে এটি একটি প্রদত্ত গ্রাফের জন্য বিস্তৃত গাছের সংখ্যা গণনা করতে ব্যবহার করা যেতে পারে। একটি গ্রাফের বিরলতম কাটা ফিডলার ভেক্টরের মাধ্যমে আনুমানিক করা যেতে পারে-গ্রাফের দ্বিতীয় ক্ষুদ্রতম আইগেনভ্যালু ল্যাপলেসিয়ানের সাথে সম্পর্কিত আইগেনভেক্টর-যা চিগারের বৈষম্য দ্বারা প্রতিষ্ঠিত। ল্যাপলেসিয়ান ম্যাট্রিক্সের বর্ণালী পচন নিম্ন মাত্রিক এম্বেডিং নির্মাণের অনুমতি দেয় যা অনেক মেশিন লার্নিং অ্যাপ্লিকেশনগুলিতে প্রদর্শিত হয় এবং গ্রাফ অঙ্কনে একটি বর্ণালী বিন্যাস নির্ধারণ করে। গ্রাফ-ভিত্তিক সংকেত প্রক্রিয়াকরণ গ্রাফ ফুরিয়ার রূপান্তরের উপর ভিত্তি করে করা হয় যা সংকেতের সাথে সম্পর্কিত গ্রাফের ল্যাপলেসিয়ান ম্যাট্রিক্সের আইগেনভেক্টরের জন্য জটিল সাইনুসয়েডের মানক ভিত্তি প্রতিস্থাপন করে ঐতিহ্যবাহী বিচ্ছিন্ন ফুরিয়ার রূপান্তরকে প্রসারিত করে। ল্যাপলেসিয়ান ম্যাট্রিক্স একটি সহজ গ্রাফের জন্য সংজ্ঞায়িত করা সবচেয়ে সহজ, তবে প্রান্ত-ওজনযুক্ত গ্রাফের জন্য অ্যাপ্লিকেশনগুলিতে আরও সাধারণ, অর্থাৎ, এর প্রান্তে ওজন সহ-গ্রাফ সংলগ্ন ম্যাট্রিক্সের এন্ট্রি। স্পেকট্রাল গ্রাফ তত্ত্ব একটি গ্রাফের বৈশিষ্ট্যগুলিকে একটি বর্ণালীর সাথে সম্পর্কিত করে, অর্থাৎ, আইগেনভ্যালু এবং গ্রাফের সাথে সম্পর্কিত ম্যাট্রিক্সের আইগেনভেক্টর, যেমন এর সংলগ্ন ম্যাট্রিক্স বা ল্যাপলেসিয়ান ম্যাট্রিক্স। ভারসাম্যহীন ওজন ম্যাট্রিক্স বর্ণালীকে অবাঞ্ছিতভাবে প্রভাবিত করতে পারে, যার ফলে স্বাভাবিককরণের প্রয়োজন হয়-ম্যাট্রিক্স এন্ট্রিগুলির একটি কলাম/সারি স্কেলিং-যার ফলে স্বাভাবিক সংলগ্নতা এবং ল্যাপলেসিয়ান ম্যাট্রিক্স হয়। সরল গ্রাফের সংজ্ঞা ল্যাপলেসিয়ান ম্যাট্রিক্স শীর্ষস্থান সহ একটি সাধারণ গ্রাফ দেওয়া হলে, এর ল্যাপলেসিয়ান ম্যাট্রিক্সকে ম্যাট্রিক্স দ্বারা উপাদান-ভিত্তিক বা সমতুল্যভাবে সংজ্ঞায়িত করা হয় যেখানে ডি হল ডিগ্রি ম্যাট্রিক্স এবং এ হল গ্রাফের সংলগ্ন ম্যাট্রিক্স। যেহেতু এটি একটি সহজ গ্রাফ, শুধুমাত্র 1s বা 0s রয়েছে এবং এর তির্যক উপাদানগুলি সমস্ত 0s। এখানে একটি লেবেলযুক্ত, অনির্দিষ্ট গ্রাফ এবং এর ল্যাপলেসিয়ান ম্যাট্রিক্সের একটি সহজ উদাহরণ রয়েছে। আমরা অনির্দিষ্ট গ্রাফের জন্য লক্ষ্য করি যে সংলগ্ন ম্যাট্রিক্স এবং ল্যাপলেসিয়ান ম্যাট্রিক্স উভয়ই প্রতিসম, এবং ল্যাপলেসিয়ান ম্যাট্রিক্সের সারি এবং কলাম-সমষ্টিগুলি সবই শূন্য। নির্দেশিত গ্রাফের জন্য, প্রয়োগের উপর নির্ভর করে ইনডিগ্রি বা আউট ডিগ্রি ব্যবহার করা যেতে পারে, যেমন নিম্নলিখিত উদাহরণেঃ নির্দেশিত গ্রাফে, সংলগ্ন ম্যাট্রিক্স এবং ল্যাপলেসিয়ান ম্যাট্রিক্স উভয়ই অসমমিত। এর ল্যাপলেসিয়ান ম্যাট্রিক্সে, কলাম-সমষ্টি বা সারি-সমষ্টি শূন্য হয়, যা নির্ভর করে ইনডিগ্রি বা আউট ডিগ্রি ব্যবহার করা হয়েছে কিনা তার উপর। আপতন ম্যাট্রিক্সের মাধ্যমে প্রতিসম ল্যাপলেসিয়ান ভার্টেক্স v এবং প্রান্ত e-এর জন্য উপাদান Bve সহ আপতন ম্যাট্রিক্স B (সংযোগকারী শীর্ষ এবং, i> j সহ) দ্বারা সংজ্ঞায়িত করা হয় যদিও এই সংজ্ঞার প্রান্তগুলি প্রযুক্তিগতভাবে নির্দেশিত, তবুও তাদের দিকগুলি নির্বিচারে হতে পারে, যার ফলে একই প্রতিসম ল্যাপলেসিয়ান ম্যাট্রিক্স L সংজ্ঞায়িত করা হয় যেখানে B-এর ম্যাট্রিক্স ট্রান্সপোজ হয়। একটি বিকল্প পণ্য তথাকথিত প্রান্ত-ভিত্তিক ল্যাপলেসিয়ানকে সংজ্ঞায়িত করে, যা একটি নির্দেশিত গ্রাফের জন্য মূল সাধারণভাবে ব্যবহৃত শীর্ষ-ভিত্তিক ল্যাপলেসিয়ান ম্যাট্রিক্স এল. সিমেট্রিক ল্যাপলেসিয়ানের বিপরীতে একটি নির্দেশিত গ্রাফের ল্যাপলেসিয়ান ম্যাট্রিক্স সংজ্ঞা অনুসারে সাধারণত অ-সিমেট্রিক, যেখানে, উদাহরণস্বরূপ, ঐতিহ্যবাহী বর্ণালী ক্লাস্টারিং প্রাথমিকভাবে সিমেট্রিক সংলগ্নতা এবং ল্যাপলেসিয়ান ম্যাট্রিক্স সহ অনির্দিষ্ট গ্রাফের জন্য তৈরি করা হয়। প্রতিসাম্যের প্রয়োজনীয় কৌশল প্রয়োগের একটি তুচ্ছ পদ্ধতি হল মূল নির্দেশিত গ্রাফটিকে একটি অনির্দিষ্ট গ্রাফে পরিণত করা এবং পরেরটির জন্য ল্যাপলেসিয়ান ম্যাট্রিক্স তৈরি করা। ম্যাট্রিক্স নোটেশনে, অনির্দিষ্ট গ্রাফের সংলগ্ন ম্যাট্রিক্সকে, উদাহরণস্বরূপ, মূল নির্দেশিত গ্রাফ এবং তার ম্যাট্রিক্স ট্রান্সপোজের সংলগ্ন ম্যাট্রিক্সের বুলিয়ান যোগফল হিসাবে সংজ্ঞায়িত করা যেতে পারে, যেখানে শূন্য এবং একটি এন্ট্রিকে সংখ্যাসূচকের পরিবর্তে যৌক্তিক হিসাবে বিবেচনা করা হয়, যেমন নিম্নলিখিত উদাহরণেঃ ল্যাপলেসিয়ান ম্যাট্রিক্স স্বাভাবিকীকরণ একটি বড় ডিগ্রি সহ একটি শীর্ষ, যাকে ভারী নোডও বলা হয়, এর ফলে ম্যাট্রিক্স বৈশিষ্ট্যগুলিতে আধিপত্য বিস্তারকারী ল্যাপলেসিয়ান ম্যাট্রিক্সে একটি বড় তির্যক এন্ট্রি হয়। ল্যাপলেসিয়ান ম্যাট্রিক্সের এন্ট্রিগুলিকে ভার্টেক্স ডিগ্রি দ্বারা ভাগ করে এই ধরনের শীর্ষগুলির প্রভাবকে অন্যান্য শীর্ষগুলির সমান করার লক্ষ্যে স্বাভাবিককরণ করা হয়। শূন্য দ্বারা বিভাজন এড়াতে, শূন্য ডিগ্রি সহ বিচ্ছিন্ন শীর্ষগুলি স্বাভাবিককরণ প্রক্রিয়া থেকে বাদ দেওয়া হয়। প্রতিসম স্বাভাবিক ল্যাপলেসিয়ান ম্যাট্রিক্সকে প্রতিসম স্বাভাবিক ল্যাপলেসিয়ান ম্যাট্রিক্স হিসাবে সংজ্ঞায়িত করা হয়ঃ যেখানে মুর-পেনরোজ বিপরীত। এর উপাদানগুলি এইভাবে দেওয়া হয়েছে প্রতিসমভাবে স্বাভাবিক ল্যাপলেসিয়ান ম্যাট্রিক্স প্রতিসম হয় যদি এবং শুধুমাত্র যদি সংলগ্ন ম্যাট্রিক্স প্রতিসম হয়। একটি নির্দেশিত গ্রাফের অ-প্রতিসম সংলগ্নতা ম্যাট্রিক্সের জন্য, অবিন্যস্ত এবং বহির্বিভাগের যে কোনও একটি স্বাভাবিককরণের জন্য ব্যবহার করা যেতে পারেঃ বাম (র্যান্ডম-ওয়াক) এবং ডান স্বাভাবিক ল্যাপলেসিয়ান বাম (র্যান্ডম-ওয়াক) স্বাভাবিক ল্যাপলেসিয়ান ম্যাট্রিক্সকে সংজ্ঞায়িত করা হয়ঃ যেখানে মুর-পেনরোজ বিপরীত। এর উপাদানগুলি দ্বারা দেওয়া হয়েছে একইভাবে, সঠিক স্বাভাবিক ল্যাপলেসিয়ান ম্যাট্রিক্স হিসাবে সংজ্ঞায়িত করা হয়। সমস্ত বিচ্ছিন্ন শীর্ষগুলির তুচ্ছ ক্ষেত্রে ব্যতীত, যদি সংলগ্ন ম্যাট্রিক্স প্রতিসম হয় তবে বাম বা ডান স্বাভাবিক ল্যাপলেসিয়ান ম্যাট্রিক্স প্রতিসম হয় না। উদাহরণস্বরূপ, উদাহরণটি আরও দেখায় যে যদি কোনও বিচ্ছিন্ন শীর্ষ না থাকে, তবে ডান দিকটি স্টোকাস্টিক এবং তাই এটি একটি র্যান্ডম ওয়াকের ম্যাট্রিক্স, যাতে বাম স্বাভাবিক ল্যাপলেসিয়ানের প্রতিটি সারির যোগফল শূন্য হয়। সুতরাং আমরা কখনও কখনও বিকল্পভাবে র্যান্ডম-ওয়াক নর্মালাইজড ল্যাপলেসিয়ান বলি। কম অস্বাভাবিকভাবে ব্যবহৃত ডান নর্মালাইজড ল্যাপলেসিয়ানে প্রতিটি কলামের যোগফল শূন্য হয় কারণ এটি বাঁদিকের স্টোকাস্টিক। একটি নির্দেশিত গ্রাফের অ-প্রতিসম সংলগ্নতা ম্যাট্রিক্সের জন্য, স্বাভাবিককরণের জন্য অনির্দিষ্ট বা বহিরাগত ডিগ্রিও বেছে নিতে হবেঃ সারি-সমষ্টি সহ বাম-ডিগ্রি স্বাভাবিক ল্যাপলেসিয়ান সমস্ত 0 ডান স্টোকাস্টিকের সাথে সম্পর্কিত, যখন ডান-ডিগ্রি স্বাভাবিক ল্যাপলেসিয়ান কলাম-সমষ্টি সহ সমস্ত 0 বাম স্টোকাস্টিক ধারণ করে। ওজনযুক্ত প্রান্ত সহ গ্রাফের সংজ্ঞা ওজনযুক্ত প্রান্ত সহ অ্যাপ্লিকেশন গ্রাফগুলিতে সাধারণভাবে তাদের সংলগ্ন ম্যাট্রিক্স দ্বারা সুবিধামত সংজ্ঞায়িত করা হয় যেখানে এন্ট্রিগুলির মানগুলি সংখ্যাসূচক এবং আর শূন্য এবং একের মধ্যে সীমাবদ্ধ নয়। বর্ণালী ক্লাস্টারিং এবং গ্রাফ-ভিত্তিক সংকেত প্রক্রিয়াকরণে, যেখানে গ্রাফের শীর্ষগুলি ডেটা পয়েন্টের প্রতিনিধিত্ব করে, প্রান্তের ওজন গণনা করা যেতে পারে, উদাহরণস্বরূপ, ডেটা পয়েন্টের জোড়ার মধ্যে দূরত্বের বিপরীত আনুপাতিক হিসাবে, যার ফলে সমস্ত ওজন অ-নেতিবাচক হয় এবং বৃহত্তর মানগুলি অনানুষ্ঠানিকভাবে আরও অনুরূপ ডেটা পয়েন্টের জোড়ার সাথে সামঞ্জস্যপূর্ণ। ডেটা পয়েন্টগুলির মধ্যে পারস্পরিক সম্পর্ক এবং বিরোধী সম্পর্ক ব্যবহার করা স্বাভাবিকভাবেই ইতিবাচক এবং নেতিবাচক উভয় ওজনের দিকে পরিচালিত করে। সহজ গ্রাফের বেশিরভাগ সংজ্ঞাগুলি অ-নেতিবাচক ওজনের স্ট্যান্ডার্ড ক্ষেত্রে তুচ্ছভাবে প্রসারিত করা হয়, যেখানে নেতিবাচক ওজনের জন্য আরও মনোযোগ প্রয়োজন, বিশেষ করে স্বাভাবিককরণের ক্ষেত্রে। ল্যাপলেসিয়ান ম্যাট্রিক্সকে সংজ্ঞায়িত করা হয় যেখানে ডি হল ডিগ্রি ম্যাট্রিক্স এবং এ হল গ্রাফের সংলগ্ন ম্যাট্রিক্স। নির্দেশিত গ্রাফগুলির জন্য, প্রয়োগের উপর নির্ভর করে ইনডিগ্রি বা আউট ডিগ্রি ব্যবহার করা যেতে পারে, যেমন নিম্নলিখিত উদাহরণেঃ গ্রাফ স্ব-লুপগুলি, যা সংলগ্ন ম্যাট্রিক্সের প্রধান তির্যকের উপর অ-শূন্য এন্ট্রি দ্বারা নিজেকে প্রকাশ করে, অনুমোদিত তবে গ্রাফ ল্যাপলেসিয়ান মানগুলিকে প্রভাবিত করে না। ইনসিডেন্স ম্যাট্রিক্সের মাধ্যমে প্রতিসম ল্যাপলেসিয়ান ভারযুক্ত প্রান্তযুক্ত গ্রাফের জন্য একটি ভারযুক্ত ইনসিডেন্স ম্যাট্রিক্স বি সংজ্ঞায়িত করা যেতে পারে এবং সংশ্লিষ্ট প্রতিসম ল্যাপলেসিয়ান হিসাবে তৈরি করতে এটি ব্যবহার করা যেতে পারে। এখানে বর্ণিত একটি বিকল্প পরিচ্ছন্ন পদ্ধতি হল সংযোগ থেকে ওজনকে আলাদা করাঃ নিয়মিত গ্রাফের জন্য আপতন ম্যাট্রিক্স ব্যবহার চালিয়ে যাওয়া এবং কেবল ওজনের মান ধারণকারী একটি ম্যাট্রিক্স প্রবর্তন করা। একটি স্প্রিং সিস্টেম এই মডেলের একটি উদাহরণ যা যান্ত্রিক ক্ষেত্রে প্রদত্ত কঠোরতা এবং একক দৈর্ঘ্যের স্প্রিংগুলির একটি সিস্টেম বর্ণনা করতে ব্যবহৃত হয়, যেখানে কঠোরতার মানগুলি গ্রাফ প্রান্তের ওজনের ভূমিকা পালন করে। এইভাবে আমরা ভারহীন আপতন ম্যাট্রিক্স B-এর সংজ্ঞাটি ভার্টেক্স v-এর জন্য উপাদান Bve-এর সাথে পুনরায় ব্যবহার করি এবং প্রান্ত e (সংযোগকারী শীর্ষ এবং, i> j-এর সাথে) দ্বারা সংজ্ঞায়িত। যদিও বি-এর সংজ্ঞার প্রান্তগুলি প্রযুক্তিগতভাবে নির্দেশিত, তবুও তাদের দিকগুলি নির্বিচারে হতে পারে, তারপরেও একই প্রতিসম ল্যাপলেসিয়ান ম্যাট্রিক্স এল হিসাবে সংজ্ঞায়িত হয় যেখানে বি-এর ম্যাট্রিক্স ট্রান্সপোজ হয়। গঠনটি নিম্নলিখিত উদাহরণে চিত্রিত করা হয়েছে, যেখানে প্রতিটি প্রান্তকে ওজন মান i বরাদ্দ করা হয়েছে, একটি নির্দেশিত গ্রাফের জন্য প্রতিসম ল্যাপলেসিয়ান ঠিক যেমন সাধারণ গ্রাফের জন্য, একটি নির্দেশিত ওজনযুক্ত গ্রাফের ল্যাপলেসিয়ান ম্যাট্রিক্স সংজ্ঞা অনুসারে সাধারণত অসমমিত হয়। ল্যাপলেসিয়ান নির্মাণের আগে মূল নির্দেশিত গ্রাফটিকে একটি অনির্দিষ্ট গ্রাফে পরিণত করে প্রতিসাম্য প্রয়োগ করা যেতে পারে। অনির্দিষ্ট গ্রাফের সংলগ্নতা ম্যাট্রিক্সকে, উদাহরণস্বরূপ, মূল নির্দেশিত গ্রাফের সংলগ্নতা ম্যাট্রিক্সের সমষ্টি হিসাবে সংজ্ঞায়িত করা যেতে পারে এবং এর ম্যাট্রিক্সকে নিম্নলিখিত উদাহরণের মতো স্থানান্তরিত করা যেতে পারেঃ যেখানে শূন্য এবং একটি এন্ট্রিগুলিকে সহজ গ্রাফের মতো যৌক্তিক হিসাবে বিবেচনা করা হয়, মানগুলি, ফলাফলের পার্থক্য ব্যাখ্যা করে-সহজ গ্রাফের জন্য, প্রতিসাম্যযুক্ত গ্রাফটি এখনও তার প্রতিসাম্যযুক্ত সংলগ্নতা ম্যাট্রিক্সের সাথে সহজ হতে হবে যার কেবল যৌক্তিক, সংখ্যাসূচক মান নেই, উদাহরণস্বরূপ, যৌক্তিক যোগফল 1 ভি 1 = 1, এবং সংখ্যাসূচক যোগফল 1 + 1 = 2। বিকল্পভাবে, দুটি ল্যাপলেসিয়ান থেকে প্রতিসম ল্যাপলেসিয়ান ম্যাট্রিক্স গণনা করা যেতে পারে ইনডিগ্রি এবং আউট ডিগ্রি ব্যবহার করে, যেমন নিম্নলিখিত উদাহরণেঃ আউট-ডিগ্রি ল্যাপলেসিয়ান ট্রান্সপোজড এবং ইন-ডিগ্রি ল্যাপলেসিয়ানের যোগফল প্রতিসম ল্যাপলেসিয়ান ম্যাট্রিক্সের সমান। ল্যাপলেসিয়ান ম্যাট্রিক্স স্বাভাবিকীকরণ স্বাভাবিককরণের লক্ষ্য হল, সাধারণ গ্রাফের মতো, ল্যাপলেসিয়ান ম্যাট্রিক্সের তির্যক এন্ট্রিগুলিকে সমস্ত একক করা, এবং অনুরূপভাবে অফ-ডায়াগোনাল এন্ট্রিগুলিকে স্কেল করা। একটি ভারযুক্ত আলেখ্যে, একটি শীর্ষে একটি বড় মাত্রা থাকতে পারে কারণ সংযুক্ত প্রান্তের সংখ্যা কম কিন্তু বড় ওজনের পাশাপাশি একক ওজনের সাথে সংযুক্ত প্রান্তের সংখ্যাও বেশি। গ্রাফ স্ব-লুপ, অর্থাৎ, সংলগ্ন ম্যাট্রিক্সের প্রধান তির্যকের অ-শূন্য এন্ট্রিগুলি গ্রাফ ল্যাপলেসিয়ান মানগুলিকে প্রভাবিত করে না, তবে স্বাভাবিককরণের কারণগুলির গণনার জন্য গণনা করা প্রয়োজন হতে পারে। প্রতিসম স্বাভাবিক ল্যাপলেসিয়ান প্রতিসম স্বাভাবিক ল্যাপলেসিয়ানকে সংজ্ঞায়িত করা হয় যেখানে এল হল অস্বাভাবিক ল্যাপলেসিয়ান, এ হল সংলগ্ন ম্যাট্রিক্স, ডি হল ডিগ্রি ম্যাট্রিক্স এবং মুর-পেনরোজ বিপরীত। যেহেতু ডিগ্রি ম্যাট্রিক্স ডি তির্যক, তাই এর পারস্পরিক বর্গমূলটি কেবল তির্যক ম্যাট্রিক্স যার তির্যক এন্ট্রিগুলি ডি এর তির্যক এন্ট্রিগুলির বর্গমূলগুলির পারস্পরিক। যদি সমস্ত প্রান্তের ওজন অ-নেতিবাচক হয় তবে সমস্ত ডিগ্রি মানগুলি স্বয়ংক্রিয়ভাবে অ-নেতিবাচক হয় এবং তাই প্রতিটি ডিগ্রি মানের একটি অনন্য ধনাত্মক বর্গমূল থাকে। শূন্য দ্বারা বিভাজন এড়ানোর জন্য, শূন্য ডিগ্রি সহ শীর্ষগুলি স্বাভাবিককরণ প্রক্রিয়া থেকে বাদ দেওয়া হয়, যেমন নিম্নলিখিত উদাহরণেঃ প্রতিসমভাবে স্বাভাবিক ল্যাপলেসিয়ান একটি প্রতিসম ম্যাট্রিক্স যদি এবং শুধুমাত্র যদি সংলগ্ন ম্যাট্রিক্স এ প্রতিসম হয় এবং ডি এর তির্যক এন্ট্রিগুলি অ-নেতিবাচক হয়, তবে আমরা প্রতিসম স্বাভাবিক ল্যাপলেসিয়ান শব্দটি ব্যবহার করতে পারি। প্রতিসম স্বাভাবিক ল্যাপলেসিয়ান ম্যাট্রিক্সকে ওজনহীন আপতন ম্যাট্রিক্স বি এবং তির্যক ম্যাট্রিক্স ডাব্লু ব্যবহার করে লেখা যেতে পারে যার প্রান্তে ওজন থাকে এবং নতুন ওজনযুক্ত আপতন ম্যাট্রিক্সকে সংজ্ঞায়িত করা হয় যার সারিগুলি শীর্ষ দ্বারা সূচীভুক্ত করা হয় এবং যার কলামগুলি জি এর প্রান্ত দ্বারা এমনভাবে সূচীভুক্ত করা হয় যে প্রতিটি কলামের প্রান্তের সাথে সম্পর্কিত প্রতিটি কলামের u এর সাথে সম্পর্কিত সারিতে একটি এন্ট্রি থাকে, v এর সাথে সম্পর্কিত সারিতে একটি এন্ট্রি এবং অন্য কোথাও 0 এন্ট্রি থাকে। র্যান্ডম ওয়াক নরমালাইজড ল্যাপলেসিয়ান র্যান্ডম ওয়াক নরমালাইজড ল্যাপলেসিয়ানকে সংজ্ঞায়িত করা হয় যেখানে ডি হল ডিগ্রি ম্যাট্রিক্স। যেহেতু ডিগ্রি ম্যাট্রিক্স ডি তির্যক, তাই এর বিপরীতটিকে কেবল একটি তির্যক ম্যাট্রিক্স হিসাবে সংজ্ঞায়িত করা হয়, যার তির্যক এন্ট্রিগুলি ডি-এর সংশ্লিষ্ট তির্যক এন্ট্রিগুলির পারস্পরিক। বিচ্ছিন্ন শীর্ষগুলির জন্য (ডিগ্রি 0 সহ), একটি সাধারণ পছন্দ হল সংশ্লিষ্ট উপাদানটিকে 0-তে সেট করা। র্যান্ডম-ওয়াক নর্মালাইজড ল্যাপলেসিয়ানের নামটি এই ম্যাট্রিক্স থেকে এসেছে, যেখানে এটি অ-নেতিবাচক ওজন ধরে নিয়ে গ্রাফের র্যান্ডম ওয়াকারের ট্রানজিশন ম্যাট্রিক্স। উদাহরণস্বরূপ, ধরা যাক i-th স্ট্যান্ডার্ড বেসিস ভেক্টর। তারপর একটি সম্ভাব্যতা ভেক্টর যা শীর্ষ থেকে একটি একক পদক্ষেপ নেওয়ার পরে একটি র্যান্ডম ওয়াকারের অবস্থানের বিতরণের প্রতিনিধিত্ব করে; অর্থাৎ। আরও সাধারণভাবে, যদি ভেক্টরটি গ্রাফের শীর্ষে একটি র্যান্ডম ওয়াকারের অবস্থানের সম্ভাব্যতা বিতরণ হয়, তবে পদক্ষেপের পরে ওয়াকারের সম্ভাব্যতা বিতরণ। র্যান্ডম ওয়াক নরমালাইজড ল্যাপলেসিয়ানকে লেফট নরমালাইজড ল্যাপলেসিয়ানও বলা যেতে পারে কারণ বাম দিকের নরমালাইজেশন ম্যাট্রিক্স দ্বারা ল্যাপলেসিয়ানকে গুণ করে নরমালাইজেশন করা হয়। এটির প্রতিটি সারির যোগফল শূন্য, কারণ এটি সঠিক স্টোকাস্টিক, ধরে নেওয়া যায় যে সমস্ত ওজন অ-নেতিবাচক। কম অস্বাভাবিকভাবে ব্যবহৃত ডান নর্মালাইজড ল্যাপলেসিয়ানে প্রতিটি কলামের যোগফল শূন্য হয় কারণ এটি বাঁদিকের স্টোকাস্টিক। একটি নির্দেশিত গ্রাফের অ-প্রতিসম সংলগ্নতা ম্যাট্রিক্সের জন্য, স্বাভাবিককরণের জন্য অনির্দিষ্ট বা বহিরাগত ডিগ্রিও বেছে নিতে হবেঃ সারি-সমষ্টি সহ বাম-ডিগ্রি স্বাভাবিক ল্যাপলেসিয়ান সমস্ত 0 ডান স্টোকাস্টিকের সাথে সম্পর্কিত, যখন ডান-ডিগ্রি স্বাভাবিক ল্যাপলেসিয়ান কলাম-সমষ্টি সহ সমস্ত 0 বাম স্টোকাস্টিক ধারণ করে। নেতিবাচক ওজন স্বাভাবিককরণের জন্য বেশ কয়েকটি চ্যালেঞ্জ উপস্থাপন করেঃ নেতিবাচক ওজনের উপস্থিতির ফলে স্বাভাবিকভাবেই অ-বিচ্ছিন্ন শীর্ষগুলির জন্য শূন্য সারি-এবং/অথবা কলাম-সমষ্টি হতে পারে। ধনাত্মক ওজনের একটি বড় সারির সমষ্টি এবং ঋণাত্মক ওজনের সমান ঋণাত্মক বড় সারির সমষ্টি সহ একটি শীর্ষ, একসঙ্গে শূন্য পর্যন্ত যোগফল, একটি ভারী নোড হিসাবে বিবেচিত হতে পারে এবং উভয় বড় মান স্কেল করা যেতে পারে, যখন তির্যক প্রবেশ শূন্য থাকে, যেমন একটি বিচ্ছিন্ন শীর্ষের জন্য। নেতিবাচক ওজনগুলি ঋণাত্মক সারি-এবং/অথবা কলাম-সমষ্টিও দিতে পারে, যাতে অ-স্বাভাবিক ল্যাপলেসিয়ান ম্যাট্রিক্সে সংশ্লিষ্ট তির্যক প্রবেশ ঋণাত্মক হয় এবং প্রতিসম স্বাভাবিকীকরণের জন্য প্রয়োজনীয় ধনাত্মক বর্গমূল বিদ্যমান থাকে না। স্বাভাবিককরণের উদ্দেশ্যে সারি-এবং/অথবা কলাম-সমষ্টিগুলির পরম মান নেওয়ার জন্য যুক্তি দেওয়া যেতে পারে, এইভাবে একটি সম্ভাব্য মান-1 কে স্বাভাবিক ল্যাপলেসিয়ান ম্যাট্রিক্সের প্রধান তির্যকের বৈধ একক এন্ট্রি হিসাবে বিবেচনা করা যেতে পারে। একটি (অনির্দিষ্ট) গ্রাফ জি এবং আইগেনভ্যালু সহ এর ল্যাপলেসিয়ান ম্যাট্রিক্স এল-এর জন্য বৈশিষ্ট্যঃ এল প্রতিসম। L হল ধনাত্মক-সমপরিমিত (অর্থাৎ সকলের জন্য)। এটি এই সত্য থেকে দেখা যায় যে ল্যাপলেসিয়ান প্রতিসম এবং তির্যকভাবে প্রভাবশালী। এল হল একটি এম-ম্যাট্রিক্স (এর অফ-ডায়াগোনাল এন্ট্রিগুলি অ-ইতিবাচক, তবুও এর আইগেনভ্যালুগুলির আসল অংশগুলি অ-নেতিবাচক)। এল-এর প্রতিটি সারির যোগফল এবং কলামের যোগফল শূন্য। প্রকৃতপক্ষে, যোগফলের মধ্যে, শীর্ষের ডিগ্রি প্রতিটি প্রতিবেশী জন্য একটি "-1" সঙ্গে যোগ করা হয়। ফলস্বরূপ, কারণ ভেক্টর সন্তুষ্ট করে এটি আরও বোঝায় যে ল্যাপলেসিয়ান ম্যাট্রিক্স একবচন। গ্রাফের সংযুক্ত উপাদানগুলির সংখ্যা হল ল্যাপলেসিয়ানের নালস্পেসের মাত্রা এবং 0 আইগেনভ্যালুয়ের বীজগাণিতিক গুণিতক। এল-এর ক্ষুদ্রতম অ-শূন্য আইগেনভ্যালু-কে বর্ণালী ব্যবধান বলা হয়। এল-এর দ্বিতীয় ক্ষুদ্রতম আইগেনভ্যালু (শূন্য হতে পারে) হল জি-এর বীজগাণিতিক সংযোগ (বা ফিডলার মান) এবং এটি একটি গ্রাফের বিরলতম কাটকে আনুমানিক করে। ল্যাপলেসিয়ান হল ফাংশনের এন-ডাইমেনশনাল ভেক্টর স্পেসের একটি অপারেটর, যেখানে জি-এর ভার্টেক্স সেট, এবং। যখন জি কে-রেগুলার হয়, তখন স্বাভাবিক ল্যাপলেসিয়ান হয়ঃ, যেখানে এ হল সংলগ্ন ম্যাট্রিক্স এবং আই হল একটি আইডেন্টিটি ম্যাট্রিক্স। একাধিক সংযুক্ত উপাদান সহ একটি গ্রাফের জন্য, এল একটি ব্লক তির্যক ম্যাট্রিক্স, যেখানে প্রতিটি ব্লক প্রতিটি উপাদানের জন্য সংশ্লিষ্ট ল্যাপলেসিয়ান ম্যাট্রিক্স, সম্ভবত শীর্ষগুলি পুনর্বিন্যাস করার পরে (অর্থাৎ। এল হল ক্রমাঙ্কন-একটি ব্লক তির্যক ম্যাট্রিক্সের অনুরূপ)। ল্যাপলেসিয়ান ম্যাট্রিক্স এল-এর ট্রেস বিবেচিত গ্রাফের প্রান্তের সংখ্যার সমান। এখন একক-আদর্শ আইগেনভেক্টর এবং সংশ্লিষ্ট আইগেনভ্যালু সহ একটি আইগেনডেকম্পোজিশন বিবেচনা করুনঃ কারণ ভেক্টরের অভ্যন্তরীণ গুণফল হিসাবে এটি লেখা যেতে পারে, এটি দেখায় যে এবং তাই এর আইগেনভ্যালুগুলি সমস্ত অ-নেতিবাচক। স্বাভাবিক প্রতিসম ল্যাপলেসিয়ানের সমস্ত আইগেনভ্যালু 0 = μ0 ≤. ≤ μn − 1 ≤ 2 কে সন্তুষ্ট করে। এই আইগেনভ্যালুগুলি (স্বাভাবিক ল্যাপলেসিয়ান বর্ণালী হিসাবে পরিচিত) সাধারণ গ্রাফের জন্য অন্যান্য গ্রাফ অপরিবর্তনীয়গুলির সাথে ভালভাবে সম্পর্কিত। কেউ পরীক্ষা করতে পারেন যেঃ, অর্থাৎ, স্বাভাবিক ল্যাপলেসিয়ানের অনুরূপ। এই কারণে, সাধারণভাবে প্রতিসম না হলেও, এর প্রকৃত আইগেনভ্যালু রয়েছে-স্বাভাবিক প্রতিসম ল্যাপলেসিয়ানের আইগেনভ্যালুগুলির মতোই। অবিচ্ছিন্ন ল্যাপলেসিয়ান অপারেটর হিসাবে ব্যাখ্যা গ্রাফ ল্যাপলেসিয়ান ম্যাট্রিক্সকে আরও একটি গ্রাফে নেতিবাচক বিচ্ছিন্ন ল্যাপলেস অপারেটরের একটি ম্যাট্রিক্স রূপ হিসাবে দেখা যেতে পারে যা সীমাবদ্ধ পার্থক্য পদ্ধতি দ্বারা প্রাপ্ত নেতিবাচক অবিচ্ছিন্ন ল্যাপলেসিয়ান অপারেটরকে আনুমানিক করে। (বিচ্ছিন্ন পয়সন সমীকরণ দেখুন) এই ব্যাখ্যায়, প্রতিটি গ্রাফ শীর্ষকে একটি গ্রিড বিন্দু হিসাবে বিবেচনা করা হয়; শীর্ষের স্থানীয় সংযোগ এই গ্রিড বিন্দুতে সীমাবদ্ধ পার্থক্য আনুমানিক স্টেনসিল নির্ধারণ করে, গ্রিডের আকার সর্বদা প্রতিটি প্রান্তের জন্য একটি, এবং কোনও গ্রিড বিন্দুতে কোনও সীমাবদ্ধতা নেই, যা সমজাতীয় নিউম্যান সীমানা শর্তের ক্ষেত্রে, অর্থাৎ মুক্ত সীমানার সাথে মিলে যায়। এই ধরনের ব্যাখ্যা একজনকে, উদাহরণস্বরূপ, অসীম সংখ্যক শীর্ষ এবং প্রান্ত সহ গ্রাফের ক্ষেত্রে ল্যাপলেসিয়ান ম্যাট্রিক্সকে সাধারণীকরণ করার অনুমতি দেয়, যা একটি অসীম আকারের ল্যাপলেসিয়ান ম্যাট্রিক্সের দিকে পরিচালিত করে। সাধারণীকরণ এবং ল্যাপলেসিয়ান ম্যাট্রিক্সের সম্প্রসারণ সাধারণীকরণ ল্যাপলেসিয়ানকে এইভাবে সংজ্ঞায়িত করা হয়েছেঃ লক্ষ্য করুন সাধারণ ল্যাপলেসিয়ান একটি সাধারণীকরণ ল্যাপলেসিয়ান। সংলগ্ন ম্যাট্রিক্সের চৌম্বকীয় ল্যাপলেসিয়ান এন্ট্রিগুলি জটিল-মূল্যবান হতে পারে, এই ক্ষেত্রে ম্যাট্রিক্স প্রতিসাম্যের ধারণাটি একটি হার্মিশিয়ান ম্যাট্রিক্স দ্বারা প্রতিস্থাপিত করা প্রয়োজন। বাস্তব ওজনের সাথে একটি নির্দেশিত গ্রাফের জন্য চৌম্বকীয় ল্যাপলেসিয়ানকে প্রতিসম ল্যাপলেসিয়ান এবং হার্মিটিয়ান ফেজ ম্যাট্রিক্সের বাস্তব প্রতিসম ম্যাট্রিক্সের হ্যাডামার্ড পণ্য হিসাবে জটিল এন্ট্রিগুলির সাথে তৈরি করা হয় যা জটিল সমতলের পর্যায়ে প্রান্তের দিকটি এনকোড করে। কোয়ান্টাম পদার্থবিজ্ঞানের প্রসঙ্গে, চৌম্বকীয় ল্যাপলেসিয়ানকে এমন অপারেটর হিসাবে ব্যাখ্যা করা যেতে পারে যা একটি গ্রাফের উপর একটি মুক্ত চার্জযুক্ত কণার ঘটনাবলী বর্ণনা করে, যা একটি চৌম্বক ক্ষেত্রের ক্রিয়া সাপেক্ষে এবং পরামিতিটিকে বৈদ্যুতিক চার্জ বলা হয়। নিম্নলিখিত উদাহরণেঃ বিকৃত ল্যাপলেসিয়ান বিকৃত ল্যাপলেসিয়ানকে সাধারণত সংজ্ঞায়িত করা হয় যেখানে আই হল আইডেন্টিটি ম্যাট্রিক্স, এ হল সংলগ্ন ম্যাট্রিক্স, ডি হল ডিগ্রি ম্যাট্রিক্স এবং এস হল একটি (জটিল-মূল্যবান) সংখ্যা। আদর্শ ল্যাপলেসিয়ান ন্যায়সঙ্গত এবং সংকেতহীন ল্যাপলেসিয়ান। সংকেতহীন ল্যাপলেসিয়ানকে সংজ্ঞায়িত করা হয় যেখানে ডিগ্রি ম্যাট্রিক্স, এবং এটি সংলগ্ন ম্যাট্রিক্স। স্বাক্ষরিত ল্যাপলেসিয়ানের মতো, সংকেতহীন ল্যাপলেসিয়ানও ধনাত্মক আধা-নির্দিষ্ট কারণ এটি আপতন ম্যাট্রিক্সের ক্ষেত্রে ফ্যাক্টর করা যেতে পারে। একটি 0-আইগেনভেক্টর থাকে যদি এবং শুধুমাত্র যদি এটির বিচ্ছিন্ন শীর্ষগুলি ব্যতীত একটি দ্বিদলীয় সংযুক্ত উপাদান থাকে। এটি হিসাবে দেখানো যেতে পারে এটির একটি সমাধান রয়েছে যেখানে এবং শুধুমাত্র যদি গ্রাফের একটি দ্বিদলীয় সংযুক্ত উপাদান থাকে। নির্দেশিত মাল্টিগ্রাফ ল্যাপলেসিয়ান ম্যাট্রিক্সের একটি এনালগ নির্দেশিত মাল্টিগ্রাফগুলির জন্য সংজ্ঞায়িত করা যেতে পারে। এই ক্ষেত্রে ল্যাপলেসিয়ান ম্যাট্রিক্স এল-কে সংজ্ঞায়িত করা হয় যেখানে ডি হল ডি-এর সাথে একটি তির্যক ম্যাট্রিক্স, আই হল ভার্টেক্স আই-এর আউটডিগ্রির সমান এবং এ হল এআই সহ একটি ম্যাট্রিক্স, জে হল আই থেকে জে (লুপ সহ) পর্যন্ত প্রান্তের সংখ্যার সমান। ওপেন সোর্স সফ্টওয়্যার বাস্তবায়ন সাইপাই নেটওয়ার্কএক্স জুলিয়া অ্যাপ্লিকেশন সফ্টওয়্যার স্কিকিট-লার্ন স্পেকট্রাল ক্লাস্টারিং পি. আই. জি. এস. পিঃ পাইথন মেগামেনে গ্রাফ সিগন্যাল প্রসেসিংঃ লক্ষ লক্ষ পয়েন্টের জন্য ম্যানিফোল্ড লার্নিং মসৃণজি ল্যাপলেসিয়ান চেঞ্জ পয়েন্ট ডিটেকশন ফর ডায়নামিক গ্রাফস (কে. ডি. ডি 2020) ল্যাপলেসিয়ান অপ্ট (ল্যাপলেসিয়ানের ওজনযুক্ত গ্রাফের দ্বিতীয় আইগেনভ্যালু সর্বাধিক করার জন্য একটি জুলিয়া প্যাকেজ) লিগ. এম. জি (বড় অনিয়মিত গ্রাফ মাল্টি গ্রিড) <আই. ডি 1> আরও দেখুন সীমাবদ্ধ ওজনযুক্ত গ্রাফের উপর কঠোরতা ম্যাট্রিক্স দূরত্ব ট্রানজিশন রেট ম্যাট্রিক্স ক্যালকুলাস গ্রাফ ফুরিয়ার রূপান্তর রেফারেন্স বীজগাণিতিক গ্রাফ তত্ত্ব ম্যাট্রিক্স সংখ্যাসূচক ডিফারেনশিয়াল সমীকরণ